home *** CD-ROM | disk | FTP | other *** search
| MacBinary | 1994-04-21 | 1.0 MB | [ONLN/HLX2] |
open in: 
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: MacBinary
(archive/macBinary).
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 10%
| dexvert
| MacBinary (archive/macBinary)
| fallback
| Supported |
| 100%
| file
| MacBinary II, inited, Wed Apr 20 09:49:51 1994, modified Thu Apr 21 08:06:22 1994, creator 'HLX2', type 'ONLN', 1012834 bytes "Collections Component" , at 0xf74e2 51229 bytes resource
| default (weak)
| |
| 99%
| file
| data
| default
| |
| 100%
| TrID
| MacBinary 2
| default (weak)
| |
| 100%
| siegfried
| fmt/1762 MacBinary (II)
| default
| |
| 100%
| lsar
| MacBinary
| default
|
|
| id metadata |
|---|
| key | value |
|---|
| macFileType | [ONLN] |
| macFileCreator | [HLX2] |
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 15 43 6f 6c 6c 65 63 | 74 69 6f 6e 73 20 43 6f |..Collec|tions Co|
|00000010| 6d 70 6f 6e 65 6e 74 00 | 00 00 00 00 00 00 00 00 |mponent.|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 4f 4e 4c 4e 48 4c 58 | 32 01 00 00 00 00 00 00 |.ONLNHLX|2.......|
|00000050| 00 00 00 00 0f 74 62 00 | 00 c8 1d a9 da e3 7f a9 |.....tb.|........|
|00000060| dc 1c be 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 7a f6 00 00 |........|....z...|
|00000080| 43 6f 6c 6c 65 63 74 69 | 6f 6e 73 20 43 6f 6d 70 |Collecti|ons Comp|
|00000090| 6f 6e 65 6e 74 0d 0d 49 | 6e 74 72 6f 64 75 63 74 |onent..I|ntroduct|
|000000a0| 69 6f 6e 0d 54 68 65 20 | 4f 50 46 20 43 6f 6c 6c |ion.The |OPF Coll|
|000000b0| 65 63 74 69 6f 6e 73 20 | 63 6f 6d 70 6f 6e 65 6e |ections |componen|
|000000c0| 74 20 69 73 20 61 20 73 | 75 62 73 65 74 20 6f 66 |t is a s|ubset of|
|000000d0| 20 74 68 65 20 43 2b 2b | 20 42 6f 6f 63 68 20 43 | the C++| Booch C|
|000000e0| 6f 6d 70 6f 6e 65 6e 74 | 73 a8 2e 20 54 68 65 20 |omponent|s.. The |
|000000f0| 43 2b 2b 20 42 6f 6f 63 | 68 20 43 6f 6d 70 6f 6e |C++ Booc|h Compon|
|00000100| 65 6e 74 73 20 70 72 6f | 76 69 64 65 20 65 66 66 |ents pro|vide eff|
|00000110| 69 63 69 65 6e 74 20 61 | 6e 64 20 61 64 61 70 74 |icient a|nd adapt|
|00000120| 61 62 6c 65 20 64 6f 6d | 61 69 6e 2d 69 6e 64 65 |able dom|ain-inde|
|00000130| 70 65 6e 64 65 6e 74 20 | 64 61 74 61 20 73 74 72 |pendent |data str|
|00000140| 75 63 74 75 72 65 73 20 | 61 6e 64 20 61 6c 67 6f |uctures |and algo|
|00000150| 72 69 74 68 6d 73 2e 20 | 54 68 65 20 63 6f 6d 70 |rithms. |The comp|
|00000160| 6f 6e 65 6e 74 20 68 61 | 73 20 62 65 65 6e 20 64 |onent ha|s been d|
|00000170| 65 73 69 67 6e 65 64 20 | 74 6f 20 74 61 6b 65 20 |esigned |to take |
|00000180| 61 64 76 61 6e 74 61 67 | 65 20 6f 66 20 43 2b 2b |advantag|e of C++|
|00000190| d5 73 20 75 6e 69 71 75 | 65 20 66 65 61 74 75 72 |.s uniqu|e featur|
|000001a0| 65 73 2c 20 70 61 72 74 | 69 63 75 6c 61 72 6c 79 |es, part|icularly|
|000001b0| 20 74 68 65 20 74 65 6d | 70 6c 61 74 65 20 66 65 | the tem|plate fe|
|000001c0| 61 74 75 72 65 20 74 68 | 61 74 20 61 6c 6c 6f 77 |ature th|at allow|
|000001d0| 73 20 79 6f 75 20 74 6f | 20 70 61 72 61 6d 65 74 |s you to| paramet|
|000001e0| 65 72 69 7a 65 20 65 61 | 63 68 20 64 61 74 61 20 |erize ea|ch data |
|000001f0| 73 74 72 75 63 74 75 72 | 65 20 77 69 74 68 20 74 |structur|e with t|
|00000200| 68 65 20 6b 69 6e 64 20 | 6f 66 20 69 74 65 6d 20 |he kind |of item |
|00000210| 69 74 20 63 6f 6e 74 61 | 69 6e 73 2e 0d 43 6f 6c |it conta|ins..Col|
|00000220| 6c 65 63 74 69 6f 6e 73 | 20 43 6f 6d 70 6f 6e 65 |lections| Compone|
|00000230| 6e 74 20 53 74 72 75 63 | 74 75 72 65 0d 44 69 72 |nt Struc|ture.Dir|
|00000240| 65 63 74 6f 72 79 0d 42 | 43 43 6f 6c 6c 65 63 0d |ectory.B|CCollec.|
|00000250| 48 65 72 69 74 61 67 65 | 0d 42 43 5f 43 4d 61 6e |Heritage|.BC_CMan|
|00000260| 61 67 65 64 09 09 32 33 | 0d 42 43 5f 43 50 6f 6f |aged..23|.BC_CPoo|
|00000270| 6c 09 09 32 35 0d 42 43 | 5f 43 55 6e 6d 61 6e 61 |l..25.BC|_CUnmana|
|00000280| 67 65 64 09 09 32 37 0d | 42 43 5f 54 42 69 6e 61 |ged..27.|BC_TBina|
|00000290| 72 79 4e 6f 64 65 09 09 | 32 33 0d 42 43 5f 54 42 |ryNode..|23.BC_TB|
|000002a0| 69 6e 61 72 79 54 72 65 | 65 09 09 33 35 0d 42 43 |inaryTre|e..35.BC|
|000002b0| 5f 54 42 69 6e 61 72 79 | 54 72 65 65 53 65 61 72 |_TBinary|TreeSear|
|000002c0| 63 68 09 09 34 31 0d 42 | 43 5f 54 43 6f 6c 6c 65 |ch..41.B|C_TColle|
|000002d0| 63 74 69 6f 6e 09 09 34 | 33 0d a5 20 42 43 5f 54 |ction..4|3.. BC_T|
|000002e0| 44 79 6e 61 6d 69 63 43 | 6f 6c 6c 65 63 74 69 6f |DynamicC|ollectio|
|000002f0| 6e 09 09 36 31 0d a5 20 | 42 43 5f 54 4f 72 64 65 |n..61.. |BC_TOrde|
|00000300| 72 65 64 43 6f 6c 6c 65 | 63 74 69 6f 6e 09 09 31 |redColle|ction..1|
|00000310| 31 37 0d a5 a5 20 42 43 | 5f 54 44 79 6e 61 6d 69 |17... BC|_TDynami|
|00000320| 63 4f 72 64 65 72 65 64 | 43 6f 6c 6c 65 63 74 69 |cOrdered|Collecti|
|00000330| 6f 6e 09 09 36 37 0d a5 | a5 20 42 43 5f 54 55 6e |on..67..|. BC_TUn|
|00000340| 62 6f 75 6e 64 65 64 4f | 72 64 65 72 65 64 43 6f |boundedO|rderedCo|
|00000350| 6c 6c 65 63 74 69 6f 6e | 09 09 32 31 31 0d a5 20 |llection|..211.. |
|00000360| 42 43 5f 54 55 6e 62 6f | 75 6e 64 65 64 43 6f 6c |BC_TUnbo|undedCol|
|00000370| 6c 65 63 74 69 6f 6e 09 | 09 31 31 37 0d 42 43 5f |lection.|.117.BC_|
|00000380| 54 43 6f 6c 6c 65 63 74 | 69 6f 6e 41 63 74 69 76 |TCollect|ionActiv|
|00000390| 65 49 74 65 72 61 74 6f | 72 09 09 34 39 0d 42 43 |eIterato|r..49.BC|
|000003a0| 5f 54 43 6f 6c 6c 65 63 | 74 69 6f 6e 50 61 73 73 |_TCollec|tionPass|
|000003b0| 69 76 65 49 74 65 72 61 | 74 6f 72 09 09 35 33 0d |iveItera|tor..53.|
|000003c0| 42 43 5f 54 44 79 6e 61 | 6d 69 63 09 09 35 35 0d |BC_TDyna|mic..55.|
|000003d0| 42 43 5f 54 4c 69 73 74 | 53 65 61 72 63 68 09 09 |BC_TList|Search..|
|000003e0| 39 37 0d a5 20 42 43 5f | 54 4f 72 64 65 72 65 64 |97.. BC_|TOrdered|
|000003f0| 4c 69 73 74 53 65 61 72 | 63 68 09 09 31 32 31 0d |ListSear|ch..121.|
|00000400| a5 20 42 43 5f 54 53 65 | 71 75 65 6e 74 69 61 6c |. BC_TSe|quential|
|00000410| 4c 69 73 74 53 65 61 72 | 63 68 09 09 31 34 39 0d |ListSear|ch..149.|
|00000420| 42 43 5f 54 4d 61 70 09 | 09 39 39 0d a5 20 42 43 |BC_TMap.|.99.. BC|
|00000430| 5f 54 44 79 6e 61 6d 69 | 63 4d 61 70 09 09 37 33 |_TDynami|cMap..73|
|00000440| 0d a5 20 42 43 5f 54 55 | 6e 62 6f 75 6e 64 65 64 |.. BC_TU|nbounded|
|00000450| 4d 61 70 09 09 37 33 0d | 42 43 5f 54 4d 61 70 41 |Map..73.|BC_TMapA|
|00000460| 63 74 69 76 65 49 74 65 | 72 61 74 6f 72 09 09 31 |ctiveIte|rator..1|
|00000470| 30 37 0d 42 43 5f 54 4d | 61 70 50 61 73 73 69 76 |07.BC_TM|apPassiv|
|00000480| 65 49 74 65 72 61 74 6f | 72 09 09 31 31 31 0d 42 |eIterato|r..111.B|
|00000490| 43 5f 54 4e 6f 64 65 09 | 09 31 31 35 0d 42 43 5f |C_TNode.|.115.BC_|
|000004a0| 54 50 61 69 72 09 09 31 | 32 37 0d 42 43 5f 54 51 |TPair..1|27.BC_TQ|
|000004b0| 75 65 75 65 09 09 31 32 | 39 0d a5 20 42 43 5f 54 |ueue..12|9.. BC_T|
|000004c0| 44 79 6e 61 6d 69 63 51 | 75 65 75 65 09 09 37 39 |DynamicQ|ueue..79|
|000004d0| 0d a5 20 42 43 5f 54 55 | 6e 62 6f 75 6e 64 65 64 |.. BC_TU|nbounded|
|000004e0| 51 75 65 75 65 09 09 32 | 31 37 0d 42 43 5f 54 51 |Queue..2|17.BC_TQ|
|000004f0| 75 65 75 65 41 63 74 69 | 76 65 49 74 65 72 61 74 |ueueActi|veIterat|
|00000500| 6f 72 09 09 31 33 35 0d | 42 43 5f 54 51 75 65 75 |or..135.|BC_TQueu|
|00000510| 65 50 61 73 73 69 76 65 | 49 74 65 72 61 74 6f 72 |ePassive|Iterator|
|00000520| 09 09 31 33 39 0d 42 43 | 5f 54 53 65 61 72 63 68 |..139.BC|_TSearch|
|00000530| 09 09 31 34 35 0d a5 20 | 42 43 5f 54 42 69 6e 61 |..145.. |BC_TBina|
|00000540| 72 79 53 65 61 72 63 68 | 09 09 33 31 0d a5 20 42 |rySearch|..31.. B|
|00000550| 43 5f 54 4f 72 64 65 72 | 65 64 53 65 61 72 63 68 |C_TOrder|edSearch|
|00000560| 09 09 31 32 33 0d a5 20 | 42 43 5f 54 53 65 71 75 |..123.. |BC_TSequ|
|00000570| 65 6e 74 69 61 6c 53 65 | 61 72 63 68 09 09 31 35 |entialSe|arch..15|
|00000580| 31 0d 42 43 5f 54 53 65 | 74 09 09 31 35 35 0d a5 |1.BC_TSe|t..155..|
|00000590| 20 42 43 5f 54 44 79 6e | 61 6d 69 63 53 65 74 09 | BC_TDyn|amicSet.|
|000005a0| 09 38 35 0d a5 20 42 43 | 5f 54 55 6e 62 6f 75 6e |.85.. BC|_TUnboun|
|000005b0| 64 65 64 53 65 74 09 09 | 32 32 33 0d 42 43 5f 54 |dedSet..|223.BC_T|
|000005c0| 53 65 74 41 63 74 69 76 | 65 49 74 65 72 61 74 6f |SetActiv|eIterato|
|000005d0| 72 09 09 31 36 33 0d 42 | 43 5f 54 53 65 74 50 61 |r..163.B|C_TSetPa|
|000005e0| 73 73 69 76 65 49 74 65 | 72 61 74 6f 72 09 09 31 |ssiveIte|rator..1|
|000005f0| 36 37 0d 42 43 5f 54 53 | 6f 72 74 09 09 31 36 39 |67.BC_TS|ort..169|
|00000600| 0d a5 20 42 43 5f 54 51 | 75 69 63 6b 53 6f 72 74 |.. BC_TQ|uickSort|
|00000610| 09 09 31 34 31 0d 42 43 | 5f 54 53 74 61 63 6b 09 |..141.BC|_TStack.|
|00000620| 09 31 37 33 0d a5 20 42 | 43 5f 54 44 79 6e 61 6d |.173.. B|C_TDynam|
|00000630| 69 63 53 74 61 63 6b 09 | 09 39 31 0d a5 20 42 43 |icStack.|.91.. BC|
|00000640| 5f 54 55 6e 62 6f 75 6e | 64 65 64 53 74 61 63 6b |_TUnboun|dedStack|
|00000650| 09 09 32 32 39 0d 42 43 | 5f 54 53 74 61 63 6b 41 |..229.BC|_TStackA|
|00000660| 63 74 69 76 65 49 74 65 | 72 61 74 6f 72 09 09 31 |ctiveIte|rator..1|
|00000670| 37 39 0d 42 43 5f 54 53 | 74 61 63 6b 50 61 73 73 |79.BC_TS|tackPass|
|00000680| 69 76 65 49 74 65 72 61 | 74 6f 72 09 09 31 38 33 |iveItera|tor..183|
|00000690| 0d 42 43 5f 54 54 61 62 | 6c 65 09 09 31 38 35 0d |.BC_TTab|le..185.|
|000006a0| 42 43 5f 54 55 6e 62 6f | 75 6e 64 65 64 09 09 31 |BC_TUnbo|unded..1|
|000006b0| 39 31 0d 43 6f 6c 6c 65 | 63 74 69 6f 6e 73 20 63 |91.Colle|ctions c|
|000006c0| 6f 6d 70 6f 6e 65 6e 74 | 20 62 61 73 65 20 63 6c |omponent| base cl|
|000006d0| 61 73 73 65 73 0d 54 68 | 65 20 63 6c 61 73 73 65 |asses.Th|e classe|
|000006e0| 73 20 6f 66 20 74 68 65 | 20 43 6f 6c 6c 65 63 74 |s of the| Collect|
|000006f0| 69 6f 6e 73 20 63 6f 6d | 70 6f 6e 65 6e 74 20 74 |ions com|ponent t|
|00000700| 68 61 74 20 79 6f 75 20 | 77 69 6c 6c 20 62 65 20 |hat you |will be |
|00000710| 6d 6f 73 74 20 63 6f 6e | 63 65 72 6e 65 64 20 77 |most con|cerned w|
|00000720| 69 74 68 20 61 72 65 20 | 74 68 65 20 64 61 74 61 |ith are |the data|
|00000730| 20 73 74 72 75 63 74 75 | 72 65 20 63 6c 61 73 73 | structu|re class|
|00000740| 65 73 20 61 6e 64 20 74 | 68 65 20 63 6c 61 73 73 |es and t|he class|
|00000750| 65 73 20 74 68 61 74 20 | 72 65 70 72 65 73 65 6e |es that |represen|
|00000760| 74 20 74 68 65 20 74 6f | 6f 6c 73 20 74 68 61 74 |t the to|ols that|
|00000770| 20 6f 70 65 72 61 74 65 | 20 6f 6e 20 74 68 6f 73 | operate| on thos|
|00000780| 65 20 73 74 72 75 63 74 | 75 72 65 73 2e 20 54 68 |e struct|ures. Th|
|00000790| 65 20 63 6c 61 73 73 65 | 73 20 64 6f 20 6e 6f 74 |e classe|s do not|
|000007a0| 20 64 65 73 63 65 6e 64 | 20 66 72 6f 6d 20 61 20 | descend| from a |
|000007b0| 73 69 6e 67 6c 65 20 72 | 6f 6f 74 2c 20 62 75 74 |single r|oot, but|
|000007c0| 20 61 72 65 20 72 61 74 | 68 65 72 20 61 6c 6c 20 | are rat|her all |
|000007d0| 61 74 20 74 68 65 20 72 | 6f 6f 74 20 6c 65 76 65 |at the r|oot leve|
|000007e0| 6c 20 6f 66 20 74 68 69 | 73 20 63 6f 6d 70 6f 6e |l of thi|s compon|
|000007f0| 65 6e 74 2e 20 4d 6f 73 | 74 20 6f 66 20 74 68 65 |ent. Mos|t of the|
|00000800| 20 73 74 72 75 63 74 75 | 72 65 73 20 68 61 76 65 | structu|res have|
|00000810| 20 61 6e 20 61 62 73 74 | 72 61 63 74 20 62 61 73 | an abst|ract bas|
|00000820| 65 20 63 6c 61 73 73 20 | 66 72 6f 6d 20 77 68 69 |e class |from whi|
|00000830| 63 68 20 74 77 6f 20 6f | 72 20 6d 6f 72 65 20 63 |ch two o|r more c|
|00000840| 6f 6e 63 72 65 74 65 20 | 63 6c 61 73 73 65 73 20 |oncrete |classes |
|00000850| 64 65 73 63 65 6e 64 2e | 20 0d 46 69 67 75 72 65 |descend.| .Figure|
|00000860| 20 31 2d 31 20 73 68 6f | 77 73 20 74 68 65 20 68 | 1-1 sho|ws the h|
|00000870| 69 65 72 61 72 63 68 79 | 20 66 6f 72 20 74 68 65 |ierarchy| for the|
|00000880| 20 63 6f 6c 6c 65 63 74 | 69 6f 6e 73 20 73 74 72 | collect|ions str|
|00000890| 75 63 74 75 72 65 73 2e | 0d 46 69 67 75 72 65 20 |uctures.|.Figure |
|000008a0| 31 15 31 20 20 43 6f 6c | 6c 65 63 74 69 6f 6e 73 |1.1 Col|lections|
|000008b0| 20 63 6f 6d 70 6f 6e 65 | 6e 74 20 73 75 70 65 72 | compone|nt super|
|000008c0| 63 6c 61 73 73 65 73 0d | 43 6f 6c 6c 65 63 74 69 |classes.|Collecti|
|000008d0| 6f 6e 73 20 63 6f 6d 70 | 6f 6e 65 6e 74 20 63 6f |ons comp|onent co|
|000008e0| 6e 63 65 70 74 73 0d 54 | 68 65 20 69 6e 64 69 76 |ncepts.T|he indiv|
|000008f0| 69 64 75 61 6c 20 63 6c | 61 73 73 65 73 20 74 68 |idual cl|asses th|
|00000900| 61 74 20 6d 61 6b 65 20 | 75 70 20 74 68 65 20 43 |at make |up the C|
|00000910| 2b 2b 20 42 6f 6f 63 68 | 20 43 6f 6d 70 6f 6e 65 |++ Booch| Compone|
|00000920| 6e 74 73 20 61 72 65 20 | 6f 72 67 61 6e 69 7a 65 |nts are |organize|
|00000930| 64 20 69 6e 74 6f 20 6f | 6e 65 20 6f 66 20 74 77 |d into o|ne of tw|
|00000940| 6f 20 6d 61 6a 6f 72 20 | 63 61 74 65 67 6f 72 69 |o major |categori|
|00000950| 65 73 3a 0d a5 09 53 74 | 72 75 63 74 75 72 65 73 |es:...St|ructures|
|00000960| 20 63 6f 6e 74 61 69 6e | 20 61 6c 6c 20 73 74 72 | contain| all str|
|00000970| 75 63 74 75 72 61 6c 20 | 61 62 73 74 72 61 63 74 |uctural |abstract|
|00000980| 69 6f 6e 73 2e 0d a5 09 | 54 6f 6f 6c 73 20 63 6f |ions....|Tools co|
|00000990| 6e 74 61 69 6e 20 61 6c | 6c 20 61 6c 67 6f 72 69 |ntain al|l algori|
|000009a0| 74 68 6d 69 63 20 61 62 | 73 74 72 61 63 74 69 6f |thmic ab|stractio|
|000009b0| 6e 73 2e 0d 49 6e 20 74 | 68 65 20 63 6f 6e 74 65 |ns..In t|he conte|
|000009c0| 78 74 20 6f 66 20 74 68 | 65 20 43 6f 6c 6c 65 63 |xt of th|e Collec|
|000009d0| 74 69 6f 6e 73 20 63 6f | 6d 70 6f 6e 65 6e 74 2c |tions co|mponent,|
|000009e0| 20 61 20 73 74 72 75 63 | 74 75 72 65 20 72 65 70 | a struc|ture rep|
|000009f0| 72 65 73 65 6e 74 73 20 | 61 20 73 69 6e 67 6c 65 |resents |a single|
|00000a00| 2c 20 63 6f 68 65 73 69 | 76 65 20 61 62 73 74 72 |, cohesi|ve abstr|
|00000a10| 61 63 74 69 6f 6e 2e 20 | 54 68 65 20 63 6f 6d 70 |action. |The comp|
|00000a20| 6f 6e 65 6e 74 20 70 72 | 6f 76 69 64 65 73 20 73 |onent pr|ovides s|
|00000a30| 74 72 75 63 74 75 72 61 | 6c 20 61 62 73 74 72 61 |tructura|l abstra|
|00000a40| 63 74 69 6f 6e 73 20 74 | 68 61 74 20 69 6e 63 6c |ctions t|hat incl|
|00000a50| 75 64 65 20 74 68 65 20 | 66 6f 6c 6c 6f 77 69 6e |ude the |followin|
|00000a60| 67 20 66 61 6d 69 6c 69 | 65 73 20 6f 66 20 63 6c |g famili|es of cl|
|00000a70| 61 73 73 20 74 65 6d 70 | 6c 61 74 65 73 3a 0d a5 |ass temp|lates:..|
|00000a80| 09 42 69 6e 61 72 79 20 | 74 72 65 65 73 20 61 72 |.Binary |trees ar|
|00000a90| 65 20 72 6f 6f 74 65 64 | 20 63 6f 6c 6c 65 63 74 |e rooted| collect|
|00000aa0| 69 6f 6e 20 6f 66 20 62 | 69 6e 61 72 79 20 6e 6f |ion of b|inary no|
|00000ab0| 64 65 73 20 77 68 69 63 | 68 20 6d 61 79 20 6e 6f |des whic|h may no|
|00000ac0| 74 20 63 6f 6e 74 61 69 | 6e 20 63 79 63 6c 65 73 |t contai|n cycles|
|00000ad0| 20 6f 72 20 63 72 6f 73 | 73 2d 72 65 66 65 72 65 | or cros|s-refere|
|00000ae0| 6e 63 65 73 3b 20 73 74 | 72 75 63 74 75 72 61 6c |nces; st|ructural|
|00000af0| 20 73 68 61 72 69 6e 67 | 20 69 73 20 70 65 72 6d | sharing| is perm|
|00000b00| 69 74 74 65 64 2e 0d a5 | 09 43 6f 6c 6c 65 63 74 |itted...|.Collect|
|00000b10| 69 6f 6e 73 20 61 72 65 | 20 69 6e 64 65 78 61 62 |ions are| indexab|
|00000b20| 6c 65 20 63 6f 6c 6c 65 | 63 74 69 6f 6e 20 6f 66 |le colle|ction of|
|00000b30| 20 69 74 65 6d 73 2c 20 | 65 69 74 68 65 72 20 75 | items, |either u|
|00000b40| 6e 6f 72 64 65 72 65 64 | 20 6f 72 20 6f 72 64 65 |nordered| or orde|
|00000b50| 72 65 64 2e 0d a5 09 4d | 61 70 73 20 61 72 65 20 |red....M|aps are |
|00000b60| 64 69 63 74 69 6f 6e 61 | 72 69 65 73 20 6f 66 20 |dictiona|ries of |
|00000b70| 69 74 65 6d 2f 76 61 6c | 75 65 20 70 61 69 72 73 |item/val|ue pairs|
|00000b80| 2e 0d a5 09 51 75 65 75 | 65 73 20 61 72 65 20 75 |....Queu|es are u|
|00000b90| 6e 6f 72 64 65 72 65 64 | 20 6f 72 20 6f 72 64 65 |nordered| or orde|
|00000ba0| 72 65 64 20 73 65 71 75 | 65 6e 63 65 73 20 6f 66 |red sequ|ences of|
|00000bb0| 20 69 74 65 6d 73 20 69 | 6e 20 77 68 69 63 68 20 | items i|n which |
|00000bc0| 69 74 65 6d 73 20 61 72 | 65 20 61 64 64 65 64 20 |items ar|e added |
|00000bd0| 6f 6e 20 6f 6e 65 20 65 | 6e 64 20 61 6e 64 20 72 |on one e|nd and r|
|00000be0| 65 6d 6f 76 65 64 20 66 | 72 6f 6d 20 74 68 65 20 |emoved f|rom the |
|00000bf0| 6f 70 70 6f 73 69 74 65 | 20 65 6e 64 2e 0d a5 09 |opposite| end....|
|00000c00| 53 65 74 73 20 61 72 65 | 20 63 6f 6c 6c 65 63 74 |Sets are| collect|
|00000c10| 69 6f 6e 73 20 6f 66 20 | 75 6e 64 75 70 6c 69 63 |ions of |unduplic|
|00000c20| 61 74 65 64 20 69 74 65 | 6d 73 2e 0d a5 09 53 74 |ated ite|ms....St|
|00000c30| 61 63 6b 73 20 61 72 65 | 20 73 65 71 75 65 6e 63 |acks are| sequenc|
|00000c40| 65 73 20 6f 66 20 69 74 | 65 6d 73 20 69 6e 20 77 |es of it|ems in w|
|00000c50| 68 69 63 68 20 69 74 65 | 6d 73 20 61 72 65 20 61 |hich ite|ms are a|
|00000c60| 64 64 65 64 20 61 6e 64 | 20 72 65 6d 6f 76 65 64 |dded and| removed|
|00000c70| 20 66 72 6f 6d 20 74 68 | 65 20 73 61 6d 65 20 65 | from th|e same e|
|00000c80| 6e 64 2e 0d 54 68 65 72 | 65 20 61 72 65 20 61 20 |nd..Ther|e are a |
|00000c90| 6e 75 6d 62 65 72 20 6f | 66 20 70 61 74 74 65 72 |number o|f patter|
|00000ca0| 6e 73 20 74 68 61 74 20 | 73 70 61 6e 20 74 68 69 |ns that |span thi|
|00000cb0| 73 20 64 65 63 6f 6d 70 | 6f 73 69 74 69 6f 6e 3a |s decomp|osition:|
|00000cc0| 20 73 6f 6d 65 20 73 74 | 72 75 63 74 75 72 65 73 | some st|ructures|
|00000cd0| 20 62 65 68 61 76 65 20 | 6c 69 6b 65 20 63 6f 6c | behave |like col|
|00000ce0| 6c 65 63 74 69 6f 6e 73 | 20 28 73 75 63 68 20 61 |lections| (such a|
|00000cf0| 73 20 73 65 74 73 29 2c | 20 77 68 69 6c 65 20 6f |s sets),| while o|
|00000d00| 74 68 65 72 73 20 62 65 | 68 61 76 65 20 6c 69 6b |thers be|have lik|
|00000d10| 65 20 73 65 71 75 65 6e | 63 65 73 20 28 73 75 63 |e sequen|ces (suc|
|00000d20| 68 20 61 73 20 73 74 61 | 63 6b 73 29 2e 20 41 6c |h as sta|cks). Al|
|00000d30| 73 6f 2c 20 74 68 65 20 | 62 69 6e 61 72 79 20 74 |so, the |binary t|
|00000d40| 72 65 65 20 73 74 72 75 | 63 74 75 72 65 20 70 65 |ree stru|cture pe|
|00000d50| 72 6d 69 74 73 20 73 74 | 72 75 63 74 75 72 61 6c |rmits st|ructural|
|00000d60| 20 73 68 61 72 69 6e 67 | 2c 20 77 68 65 72 65 61 | sharing|, wherea|
|00000d70| 73 20 74 68 65 20 6f 74 | 68 65 72 20 73 74 72 75 |s the ot|her stru|
|00000d80| 63 74 75 72 65 73 20 61 | 72 65 20 6d 6f 72 65 20 |ctures a|re more |
|00000d90| 6d 6f 6e 6f 6c 69 74 68 | 69 63 20 61 6e 64 20 64 |monolith|ic and d|
|00000da0| 6f 20 6e 6f 74 20 70 65 | 72 6d 69 74 20 74 68 65 |o not pe|rmit the|
|00000db0| 20 73 74 72 75 63 74 75 | 72 61 6c 20 73 68 61 72 | structu|ral shar|
|00000dc0| 69 6e 67 20 6f 66 20 74 | 68 65 69 72 20 70 61 72 |ing of t|heir par|
|00000dd0| 74 73 2e 0d 54 68 65 72 | 65 20 61 72 65 20 61 6c |ts..Ther|e are al|
|00000de0| 73 6f 20 66 75 6e 63 74 | 69 6f 6e 61 6c 20 76 61 |so funct|ional va|
|00000df0| 72 69 61 74 69 6f 6e 73 | 20 66 6f 72 20 73 6f 6d |riations| for som|
|00000e00| 65 20 63 6c 61 73 73 65 | 73 3b 20 69 6e 20 70 61 |e classe|s; in pa|
|00000e10| 72 74 69 63 75 6c 61 72 | 2c 20 6f 72 64 65 72 65 |rticular|, ordere|
|00000e20| 64 20 63 6f 6c 6c 65 63 | 74 69 6f 6e 73 20 61 6e |d collec|tions an|
|00000e30| 64 20 71 75 65 75 65 73 | 2e 20 53 69 6d 70 6c 65 |d queues|. Simple|
|00000e40| 20 63 6f 6c 6c 65 63 74 | 69 6f 6e 73 20 61 6e 64 | collect|ions and|
|00000e50| 20 71 75 65 75 65 73 20 | 61 72 65 20 6f 72 64 65 | queues |are orde|
|00000e60| 72 65 64 20 61 63 63 6f | 72 64 69 6e 67 20 74 6f |red acco|rding to|
|00000e70| 20 74 68 65 20 6f 72 64 | 65 72 20 69 6e 20 77 68 | the ord|er in wh|
|00000e80| 69 63 68 20 69 74 65 6d | 73 20 61 72 65 20 61 64 |ich item|s are ad|
|00000e90| 64 65 64 20 74 6f 20 74 | 68 65 20 73 74 72 75 63 |ded to t|he struc|
|00000ea0| 74 75 72 65 3b 20 70 72 | 69 6f 72 69 74 79 20 76 |ture; pr|iority v|
|00000eb0| 61 72 69 61 74 69 6f 6e | 73 20 61 72 65 20 6f 72 |ariation|s are or|
|00000ec0| 64 65 72 65 64 20 61 63 | 63 6f 72 64 69 6e 67 20 |dered ac|cording |
|00000ed0| 74 6f 20 73 6f 6d 65 20 | 6f 72 64 65 72 69 6e 67 |to some |ordering|
|00000ee0| 20 66 75 6e 63 74 69 6f | 6e 20 6f 66 20 74 68 65 | functio|n of the|
|00000ef0| 20 69 74 65 6d 73 20 74 | 68 65 6d 73 65 6c 76 65 | items t|hemselve|
|00000f00| 73 2e 0d 54 68 65 20 74 | 6f 6f 6c 73 20 74 68 61 |s..The t|ools tha|
|00000f10| 74 20 77 6f 72 6b 20 6f | 6e 20 74 68 65 20 73 74 |t work o|n the st|
|00000f20| 72 75 63 74 75 72 65 73 | 20 69 6e 63 6c 75 64 65 |ructures| include|
|00000f30| 20 74 68 65 20 66 6f 6c | 6c 6f 77 69 6e 67 20 66 | the fol|lowing f|
|00000f40| 61 6d 69 6c 69 65 73 20 | 6f 66 20 63 6c 61 73 73 |amilies |of class|
|00000f50| 65 73 3a 0d a5 09 53 65 | 61 72 63 68 69 6e 67 3b |es:...Se|arching;|
|00000f60| 20 6f 70 65 72 61 74 69 | 6f 6e 73 20 66 6f 72 20 | operati|ons for |
|00000f70| 73 65 61 72 63 68 69 6e | 67 20 66 6f 72 20 69 74 |searchin|g for it|
|00000f80| 65 6d 73 20 77 69 74 68 | 69 6e 20 73 74 72 75 63 |ems with|in struc|
|00000f90| 74 75 72 65 73 0d a5 09 | 53 6f 72 74 69 6e 67 3b |tures...|Sorting;|
|00000fa0| 20 6f 70 65 72 61 74 69 | 6f 6e 73 20 66 6f 72 20 | operati|ons for |
|00000fb0| 6f 72 64 65 72 69 6e 67 | 20 73 74 72 75 63 74 75 |ordering| structu|
|00000fc0| 72 65 73 0d 54 68 65 20 | 43 6f 6c 6c 65 63 74 69 |res.The |Collecti|
|00000fd0| 6f 6e 73 20 63 6f 6d 70 | 6f 6e 65 6e 74 20 61 6c |ons comp|onent al|
|00000fe0| 73 6f 20 70 72 6f 76 69 | 64 65 73 20 69 74 65 72 |so provi|des iter|
|00000ff0| 61 74 6f 72 73 2c 20 77 | 68 69 63 68 20 61 6c 6c |ators, w|hich all|
|00001000| 6f 77 20 79 6f 75 20 74 | 6f 20 61 70 70 6c 79 20 |ow you t|o apply |
|00001010| 74 68 65 20 73 61 6d 65 | 20 6f 70 65 72 61 74 69 |the same| operati|
|00001020| 6f 6e 20 6f 6e 20 61 6c | 6c 20 6f 66 20 74 68 65 |on on al|l of the|
|00001030| 20 69 74 65 6d 73 20 6f | 66 20 61 20 73 74 72 75 | items o|f a stru|
|00001040| 63 74 75 72 65 2e 0d 4f | 72 67 61 6e 69 7a 61 74 |cture..O|rganizat|
|00001050| 69 6f 6e 0d 54 68 65 20 | 43 6f 6c 6c 65 63 74 69 |ion.The |Collecti|
|00001060| 6f 6e 73 20 63 6f 6d 70 | 6f 6e 65 6e 74 20 70 6c |ons comp|onent pl|
|00001070| 61 63 65 73 20 65 61 63 | 68 20 63 6c 75 73 74 65 |aces eac|h cluste|
|00001080| 72 20 6f 66 20 63 6c 61 | 73 73 65 73 20 69 6e 74 |r of cla|sses int|
|00001090| 6f 20 69 74 73 20 6f 77 | 6e 20 63 61 74 65 67 6f |o its ow|n catego|
|000010a0| 72 79 2c 20 61 6e 64 20 | 6d 61 6b 65 73 20 61 20 |ry, and |makes a |
|000010b0| 63 6c 65 61 72 20 64 69 | 73 74 69 6e 63 74 69 6f |clear di|stinctio|
|000010c0| 6e 20 62 65 74 77 65 65 | 6e 20 70 6f 6c 69 63 79 |n betwee|n policy|
|000010d0| 20 61 6e 64 20 69 6d 70 | 6c 65 6d 65 6e 74 61 74 | and imp|lementat|
|000010e0| 69 6f 6e 2e 20 41 62 73 | 74 72 61 63 74 69 6f 6e |ion. Abs|traction|
|000010f0| 73 20 73 75 63 68 20 61 | 73 20 71 75 65 75 65 73 |s such a|s queues|
|00001100| 20 61 6e 64 20 73 65 74 | 73 20 72 65 70 72 65 73 | and set|s repres|
|00001110| 65 6e 74 20 70 61 72 74 | 69 63 75 6c 61 72 20 70 |ent part|icular p|
|00001120| 6f 6c 69 63 69 65 73 20 | 66 6f 72 20 75 73 69 6e |olicies |for usin|
|00001130| 67 20 6c 6f 77 65 72 2d | 6c 65 76 65 6c 20 73 74 |g lower-|level st|
|00001140| 72 75 63 74 75 72 65 73 | 20 73 75 63 68 20 61 73 |ructures| such as|
|00001150| 20 61 72 72 61 79 73 2e | 20 0d 46 6f 72 20 65 78 | arrays.| .For ex|
|00001160| 61 6d 70 6c 65 2c 20 61 | 20 71 75 65 75 65 20 64 |ample, a| queue d|
|00001170| 65 66 69 6e 65 73 20 74 | 68 65 20 70 6f 6c 69 63 |efines t|he polic|
|00001180| 79 20 77 68 65 72 65 20 | 69 74 65 6d 73 20 63 61 |y where |items ca|
|00001190| 6e 20 6f 6e 6c 79 20 62 | 65 20 61 64 64 65 64 20 |n only b|e added |
|000011a0| 74 6f 20 6f 6e 65 20 65 | 6e 64 20 6f 66 20 61 20 |to one e|nd of a |
|000011b0| 73 74 72 75 63 74 75 72 | 65 2c 20 61 6e 64 20 72 |structur|e, and r|
|000011c0| 65 6d 6f 76 65 64 20 66 | 72 6f 6d 20 74 68 65 20 |emoved f|rom the |
|000011d0| 6f 74 68 65 72 2e 20 41 | 20 73 65 74 2c 20 6f 6e |other. A| set, on|
|000011e0| 20 74 68 65 20 6f 74 68 | 65 72 20 68 61 6e 64 2c | the oth|er hand,|
|000011f0| 20 65 6e 66 6f 72 63 65 | 73 20 6e 6f 20 73 75 63 | enforce|s no suc|
|00001200| 68 20 70 6f 6c 69 63 79 | 20 72 65 71 75 69 72 69 |h policy| requiri|
|00001210| 6e 67 20 61 6e 20 6f 72 | 64 65 72 69 6e 67 20 6f |ng an or|dering o|
|00001220| 66 20 69 74 65 6d 73 2e | 20 54 68 75 73 2c 20 6d |f items.| Thus, m|
|00001230| 6f 72 65 20 70 72 69 6d | 69 74 69 76 65 20 61 62 |ore prim|itive ab|
|00001240| 73 74 72 61 63 74 69 6f | 6e 73 20 61 72 65 20 67 |stractio|ns are g|
|00001250| 61 74 68 65 72 65 64 20 | 74 6f 67 65 74 68 65 72 |athered |together|
|00001260| 20 61 6e 64 20 74 68 65 | 6e 20 75 73 65 64 20 66 | and the|n used f|
|00001270| 6f 72 20 64 69 66 66 65 | 72 65 6e 74 20 70 6f 6c |or diffe|rent pol|
|00001280| 69 63 69 65 73 2e 0d 47 | 65 6e 65 72 61 6c 6c 79 |icies..G|enerally|
|00001290| 2c 20 79 6f 75 20 6e 65 | 65 64 20 6f 6e 6c 79 20 |, you ne|ed only |
|000012a0| 63 6f 6e 63 65 72 6e 20 | 79 6f 75 72 73 65 6c 66 |concern |yourself|
|000012b0| 20 77 69 74 68 20 74 68 | 65 20 63 6c 61 73 73 65 | with th|e classe|
|000012c0| 73 20 66 6f 75 6e 64 20 | 69 6e 20 74 68 65 20 73 |s found |in the s|
|000012d0| 74 72 75 63 74 75 72 65 | 73 20 61 6e 64 20 74 6f |tructure|s and to|
|000012e0| 6f 6c 73 20 63 61 74 65 | 67 6f 72 69 65 73 2e 20 |ols cate|gories. |
|000012f0| 59 6f 75 20 6d 61 79 2c | 20 68 6f 77 65 76 65 72 |You may,| however|
|00001300| 2c 20 77 69 73 68 20 74 | 6f 20 6d 61 6b 65 20 75 |, wish t|o make u|
|00001310| 73 65 20 6f 66 20 74 68 | 65 20 6d 6f 72 65 20 70 |se of th|e more p|
|00001320| 72 69 6d 69 74 69 76 65 | 20 61 62 73 74 72 61 63 |rimitive| abstrac|
|00001330| 74 69 6f 6e 73 20 66 72 | 6f 6d 20 77 68 69 63 68 |tions fr|om which|
|00001340| 20 6e 65 77 20 63 6c 61 | 73 73 65 73 20 6d 61 79 | new cla|sses may|
|00001350| 20 62 65 20 63 6f 6e 73 | 74 72 75 63 74 65 64 2c | be cons|tructed,|
|00001360| 20 6f 72 20 74 68 72 6f | 75 67 68 20 77 68 69 63 | or thro|ugh whic|
|00001370| 68 20 74 68 65 20 62 65 | 68 61 76 69 6f 72 20 6f |h the be|havior o|
|00001380| 66 20 65 78 69 73 74 69 | 6e 67 20 63 6c 61 73 73 |f existi|ng class|
|00001390| 65 73 20 6d 61 79 20 62 | 65 20 6d 6f 64 69 66 69 |es may b|e modifi|
|000013a0| 65 64 2e 0d 43 6c 61 73 | 73 20 46 61 6d 69 6c 69 |ed..Clas|s Famili|
|000013b0| 65 73 0d 41 6e 6f 74 68 | 65 72 20 63 65 6e 74 72 |es.Anoth|er centr|
|000013c0| 61 6c 20 63 6f 6e 63 65 | 70 74 20 6f 66 20 74 68 |al conce|pt of th|
|000013d0| 65 20 43 6f 6c 6c 65 63 | 74 69 6f 6e 73 20 63 6f |e Collec|tions co|
|000013e0| 6d 70 6f 6e 65 6e 74 20 | 69 73 20 74 68 61 74 20 |mponent |is that |
|000013f0| 6f 66 20 62 75 69 6c 64 | 69 6e 67 20 66 61 6d 69 |of build|ing fami|
|00001400| 6c 69 65 73 20 6f 66 20 | 63 6c 61 73 73 65 73 2c |lies of |classes,|
|00001410| 20 72 65 6c 61 74 65 64 | 20 62 79 20 6c 69 6e 65 | related| by line|
|00001420| 73 20 6f 66 20 69 6e 68 | 65 72 69 74 61 6e 63 65 |s of inh|eritance|
|00001430| 2e 20 46 6f 72 20 65 61 | 63 68 20 6b 69 6e 64 20 |. For ea|ch kind |
|00001440| 6f 66 20 73 74 72 75 63 | 74 75 72 65 2c 20 74 68 |of struc|ture, th|
|00001450| 65 72 65 20 69 73 20 61 | 6e 20 61 62 73 74 72 61 |ere is a|n abstra|
|00001460| 63 74 20 62 61 73 65 20 | 63 6c 61 73 73 20 77 69 |ct base |class wi|
|00001470| 74 68 20 73 65 76 65 72 | 61 6c 20 63 6f 6e 63 72 |th sever|al concr|
|00001480| 65 74 65 20 73 75 62 63 | 6c 61 73 73 65 73 2e 20 |ete subc|lasses. |
|00001490| 45 61 63 68 20 6f 66 20 | 74 68 65 20 73 75 62 63 |Each of |the subc|
|000014a0| 6c 61 73 73 65 73 20 68 | 61 73 20 61 20 73 6c 69 |lasses h|as a sli|
|000014b0| 67 68 74 6c 79 20 64 69 | 66 66 65 72 65 6e 74 20 |ghtly di|fferent |
|000014c0| 72 65 70 72 65 73 65 6e | 74 61 74 69 6f 6e 2c 20 |represen|tation, |
|000014d0| 61 6e 64 20 74 68 65 72 | 65 66 6f 72 65 20 68 61 |and ther|efore ha|
|000014e0| 73 20 64 69 66 66 65 72 | 65 6e 74 20 74 69 6d 65 |s differ|ent time|
|000014f0| 20 61 6e 64 20 73 70 61 | 63 65 20 73 65 6d 61 6e | and spa|ce seman|
|00001500| 74 69 63 73 2e 20 54 68 | 75 73 2c 20 79 6f 75 20 |tics. Th|us, you |
|00001510| 63 61 6e 20 73 65 6c 65 | 63 74 20 74 68 65 20 63 |can sele|ct the c|
|00001520| 6f 6e 63 72 65 74 65 20 | 63 6c 61 73 73 20 77 68 |oncrete |class wh|
|00001530| 6f 73 65 20 74 69 6d 65 | 20 61 6e 64 20 73 70 61 |ose time| and spa|
|00001540| 63 65 20 73 65 6d 61 6e | 74 69 63 73 20 62 65 73 |ce seman|tics bes|
|00001550| 74 20 66 69 74 20 79 6f | 75 72 20 6e 65 65 64 73 |t fit yo|ur needs|
|00001560| 2c 20 79 65 74 20 73 74 | 69 6c 6c 20 62 65 20 63 |, yet st|ill be c|
|00001570| 6f 6e 66 69 64 65 6e 74 | 20 74 68 61 74 20 74 68 |onfident| that th|
|00001580| 61 74 20 63 6c 61 73 73 | 20 77 69 6c 6c 20 62 65 |at class| will be|
|00001590| 20 66 75 6e 63 74 69 6f | 6e 61 6c 6c 79 20 74 68 | functio|nally th|
|000015a0| 65 20 73 61 6d 65 20 61 | 73 20 61 6e 79 20 6f 74 |e same a|s any ot|
|000015b0| 68 65 72 20 63 6f 6e 63 | 72 65 74 65 20 63 6c 61 |her conc|rete cla|
|000015c0| 73 73 20 69 6e 20 74 68 | 65 20 66 61 6d 69 6c 79 |ss in th|e family|
|000015d0| 2e 0d 54 68 69 73 20 73 | 65 70 61 72 61 74 69 6f |..This s|eparatio|
|000015e0| 6e 20 6f 66 20 63 6f 6e | 63 65 72 6e 73 20 62 65 |n of con|cerns be|
|000015f0| 74 77 65 65 6e 20 61 6e | 20 61 62 73 74 72 61 63 |tween an| abstrac|
|00001600| 74 20 62 61 73 65 20 63 | 6c 61 73 73 20 61 6e 64 |t base c|lass and|
|00001610| 20 69 74 73 20 63 6f 6e | 63 72 65 74 65 20 63 6c | its con|crete cl|
|00001620| 61 73 73 65 73 20 61 6c | 6c 6f 77 73 20 79 6f 75 |asses al|lows you|
|00001630| 20 74 6f 20 69 6e 69 74 | 69 61 6c 6c 79 20 73 65 | to init|ially se|
|00001640| 6c 65 63 74 20 6f 6e 65 | 20 63 6f 6e 63 72 65 74 |lect one| concret|
|00001650| 65 20 63 6c 61 73 73 20 | 61 6e 64 20 6c 61 74 65 |e class |and late|
|00001660| 72 2c 20 61 73 20 74 68 | 65 20 61 70 70 6c 69 63 |r, as th|e applic|
|00001670| 61 74 69 6f 6e 20 69 73 | 20 62 65 69 6e 67 20 74 |ation is| being t|
|00001680| 75 6e 65 64 2c 20 72 65 | 70 6c 61 63 65 20 69 74 |uned, re|place it|
|00001690| 20 77 69 74 68 20 61 20 | 73 69 62 6c 69 6e 67 20 | with a |sibling |
|000016a0| 63 6f 6e 63 72 65 74 65 | 20 63 6c 61 73 73 20 77 |concrete| class w|
|000016b0| 69 74 68 20 6d 69 6e 69 | 6d 61 6c 20 65 66 66 6f |ith mini|mal effo|
|000016c0| 72 74 2e 20 59 6f 75 20 | 63 61 6e 20 62 65 20 63 |rt. You |can be c|
|000016d0| 6f 6e 66 69 64 65 6e 74 | 20 74 68 61 74 20 74 68 |onfident| that th|
|000016e0| 65 20 61 70 70 6c 69 63 | 61 74 69 6f 6e 20 77 69 |e applic|ation wi|
|000016f0| 6c 6c 20 73 74 69 6c 6c | 20 77 6f 72 6b 2c 20 62 |ll still| work, b|
|00001700| 65 63 61 75 73 65 20 61 | 6c 6c 20 73 69 62 6c 69 |ecause a|ll sibli|
|00001710| 6e 67 20 63 6f 6e 63 72 | 65 74 65 20 63 6c 61 73 |ng concr|ete clas|
|00001720| 73 65 73 20 73 68 61 72 | 65 20 74 68 65 20 73 61 |ses shar|e the sa|
|00001730| 6d 65 20 69 6e 74 65 72 | 66 61 63 65 20 61 6e 64 |me inter|face and|
|00001740| 20 74 68 65 20 73 61 6d | 65 20 62 61 73 69 63 20 | the sam|e basic |
|00001750| 62 65 68 61 76 69 6f 72 | 2e 20 41 6e 6f 74 68 65 |behavior|. Anothe|
|00001760| 72 20 69 6d 70 6c 69 63 | 61 74 69 6f 6e 20 6f 66 |r implic|ation of|
|00001770| 20 74 68 69 73 20 6f 72 | 67 61 6e 69 7a 61 74 69 | this or|ganizati|
|00001780| 6f 6e 20 69 73 20 74 68 | 61 74 20 69 74 20 6d 61 |on is th|at it ma|
|00001790| 6b 65 73 20 69 74 20 70 | 6f 73 73 69 62 6c 65 20 |kes it p|ossible |
|000017a0| 74 6f 20 63 6f 70 79 2c | 20 61 73 73 69 67 6e 2c |to copy,| assign,|
|000017b0| 20 61 6e 64 20 74 65 73 | 74 20 66 6f 72 20 65 71 | and tes|t for eq|
|000017c0| 75 61 6c 69 74 79 20 61 | 6d 6f 6e 67 20 6f 62 6a |uality a|mong obj|
|000017d0| 65 63 74 73 20 6f 66 20 | 74 68 65 20 73 61 6d 65 |ects of |the same|
|000017e0| 20 66 61 6d 69 6c 79 20 | 6f 66 20 63 6c 61 73 73 | family |of class|
|000017f0| 65 73 2c 20 65 76 65 6e | 20 69 66 20 65 61 63 68 |es, even| if each|
|00001800| 20 6f 62 6a 65 63 74 20 | 68 61 73 20 61 20 72 61 | object |has a ra|
|00001810| 64 69 63 61 6c 6c 79 20 | 64 69 66 66 65 72 65 6e |dically |differen|
|00001820| 74 20 72 65 70 72 65 73 | 65 6e 74 61 74 69 6f 6e |t repres|entation|
|00001830| 2e 0d 49 6e 20 61 20 73 | 65 6e 73 65 2c 20 61 6e |..In a s|ense, an|
|00001840| 20 61 62 73 74 72 61 63 | 74 20 62 61 73 65 20 63 | abstrac|t base c|
|00001850| 6c 61 73 73 20 74 68 75 | 73 20 63 61 70 74 75 72 |lass thu|s captur|
|00001860| 65 73 20 61 6c 6c 20 72 | 65 6c 65 76 61 6e 74 20 |es all r|elevant |
|00001870| 70 75 62 6c 69 63 20 64 | 65 73 69 67 6e 20 64 65 |public d|esign de|
|00001880| 63 69 73 69 6f 6e 73 20 | 61 62 6f 75 74 20 61 6e |cisions |about an|
|00001890| 20 61 62 73 74 72 61 63 | 74 69 6f 6e 2e 20 41 6e | abstrac|tion. An|
|000018a0| 6f 74 68 65 72 20 75 73 | 65 20 6f 66 20 61 62 73 |other us|e of abs|
|000018b0| 74 72 61 63 74 20 62 61 | 73 65 20 63 6c 61 73 73 |tract ba|se class|
|000018c0| 65 73 20 69 73 20 74 6f | 20 63 61 63 68 65 20 63 |es is to| cache c|
|000018d0| 6f 6d 6d 6f 6e 20 73 74 | 61 74 65 20 74 68 61 74 |ommon st|ate that|
|000018e0| 20 6d 69 67 68 74 20 6f | 74 68 65 72 77 69 73 65 | might o|therwise|
|000018f0| 20 62 65 20 65 78 70 65 | 6e 73 69 76 65 20 74 6f | be expe|nsive to|
|00001900| 20 63 6f 6d 70 75 74 65 | 2e 20 54 68 65 20 63 6f | compute|. The co|
|00001910| 73 74 20 6f 66 20 74 68 | 69 73 20 73 74 79 6c 65 |st of th|is style|
|00001920| 20 69 73 20 74 68 65 20 | 72 65 71 75 69 72 65 64 | is the |required|
|00001930| 20 63 6f 6f 70 65 72 61 | 74 69 6f 6e 20 62 65 74 | coopera|tion bet|
|00001940| 77 65 65 6e 20 74 68 65 | 20 61 62 73 74 72 61 63 |ween the| abstrac|
|00001950| 74 20 62 61 73 65 20 63 | 6c 61 73 73 20 61 6e 64 |t base c|lass and|
|00001960| 20 69 74 73 20 73 75 62 | 63 6c 61 73 73 65 73 2c | its sub|classes,|
|00001970| 20 74 6f 20 6b 65 65 70 | 20 74 68 65 20 63 61 63 | to keep| the cac|
|00001980| 68 65 64 20 72 65 73 75 | 6c 74 20 75 70 20 74 6f |hed resu|lt up to|
|00001990| 20 64 61 74 65 2e 0d 4d | 6f 6e 6f 6c 69 74 68 69 | date..M|onolithi|
|000019a0| 63 20 61 6e 64 20 70 6f | 6c 79 6c 69 74 68 69 63 |c and po|lylithic|
|000019b0| 20 73 74 72 75 63 74 75 | 72 65 73 0d 54 68 65 20 | structu|res.The |
|000019c0| 43 6f 6c 6c 65 63 74 69 | 6f 6e 73 20 63 6f 6d 70 |Collecti|ons comp|
|000019d0| 6f 6e 65 6e 74 20 63 6f | 6e 74 61 69 6e 73 20 62 |onent co|ntains b|
|000019e0| 6f 74 68 20 6d 6f 6e 6f | 6c 69 74 68 69 63 20 61 |oth mono|lithic a|
|000019f0| 6e 64 20 70 6f 6c 79 6c | 69 74 68 69 63 20 73 74 |nd polyl|ithic st|
|00001a00| 72 75 63 74 75 72 65 73 | 2e 20 41 20 6d 6f 6e 6f |ructures|. A mono|
|00001a10| 6c 69 74 68 69 63 20 73 | 74 72 75 63 74 75 72 65 |lithic s|tructure|
|00001a20| 20 69 73 20 6f 6e 65 20 | 74 68 61 74 20 69 73 20 | is one |that is |
|00001a30| 61 6c 77 61 79 73 20 74 | 72 65 61 74 65 64 20 61 |always t|reated a|
|00001a40| 73 20 61 20 73 69 6e 67 | 6c 65 20 75 6e 69 74 3a |s a sing|le unit:|
|00001a50| 20 74 68 65 72 65 20 61 | 72 65 20 6e 6f 20 69 64 | there a|re no id|
|00001a60| 65 6e 74 69 66 69 61 62 | 6c 65 2c 20 64 69 73 74 |entifiab|le, dist|
|00001a70| 69 6e 63 74 20 63 6f 6d | 70 6f 6e 65 6e 74 73 2c |inct com|ponents,|
|00001a80| 20 61 6e 64 20 74 68 75 | 73 20 72 65 66 65 72 65 | and thu|s refere|
|00001a90| 6e 74 69 61 6c 20 69 6e | 74 65 67 72 69 74 79 20 |ntial in|tegrity |
|00001aa0| 69 73 20 67 75 61 72 61 | 6e 74 65 65 64 2e 20 41 |is guara|nteed. A|
|00001ab0| 6c 74 65 72 6e 61 74 69 | 76 65 6c 79 2c 20 61 20 |lternati|vely, a |
|00001ac0| 70 6f 6c 79 6c 69 74 68 | 69 63 20 73 74 72 75 63 |polylith|ic struc|
|00001ad0| 74 75 72 65 20 69 73 20 | 6f 6e 65 20 69 6e 20 77 |ture is |one in w|
|00001ae0| 68 69 63 68 20 73 74 72 | 75 63 74 75 72 61 6c 20 |hich str|uctural |
|00001af0| 73 68 61 72 69 6e 67 20 | 69 73 20 70 65 72 6d 69 |sharing |is permi|
|00001b00| 74 74 65 64 2e 20 0d 54 | 68 65 20 66 75 6e 64 61 |tted. .T|he funda|
|00001b10| 6d 65 6e 74 61 6c 20 64 | 69 73 74 69 6e 63 74 69 |mental d|istincti|
|00001b20| 6f 6e 20 62 65 74 77 65 | 65 6e 20 6d 6f 6e 6f 6c |on betwe|en monol|
|00001b30| 69 74 68 69 63 20 61 6e | 64 20 70 6f 6c 79 6c 69 |ithic an|d polyli|
|00001b40| 74 68 69 63 20 73 74 72 | 75 63 74 75 72 65 73 20 |thic str|uctures |
|00001b50| 69 73 20 74 68 61 74 2c | 20 69 6e 20 6d 6f 6e 6f |is that,| in mono|
|00001b60| 6c 69 74 68 69 63 20 73 | 74 72 75 63 74 75 72 65 |lithic s|tructure|
|00001b70| 73 2c 20 74 68 65 20 73 | 65 6d 61 6e 74 69 63 73 |s, the s|emantics|
|00001b80| 20 6f 66 20 63 6f 70 79 | 69 6e 67 2c 20 61 73 73 | of copy|ing, ass|
|00001b90| 69 67 6e 6d 65 6e 74 2c | 20 61 6e 64 20 65 71 75 |ignment,| and equ|
|00001ba0| 61 6c 69 74 79 20 61 72 | 65 20 64 65 65 70 2c 20 |ality ar|e deep, |
|00001bb0| 77 68 65 72 65 61 73 20 | 69 6e 20 70 6f 6c 79 6c |whereas |in polyl|
|00001bc0| 69 74 68 69 63 20 73 74 | 72 75 63 74 75 72 65 73 |ithic st|ructures|
|00001bd0| 2c 20 63 6f 70 79 69 6e | 67 2c 20 61 73 73 69 67 |, copyin|g, assig|
|00001be0| 6e 6d 65 6e 74 2c 20 61 | 6e 64 20 65 71 75 61 6c |nment, a|nd equal|
|00001bf0| 69 74 79 20 61 72 65 20 | 61 6c 6c 20 73 68 61 6c |ity are |all shal|
|00001c00| 6c 6f 77 20 28 6d 65 61 | 6e 69 6e 67 20 74 68 61 |low (mea|ning tha|
|00001c10| 74 20 61 6c 69 61 73 65 | 73 20 6d 61 79 20 73 68 |t aliase|s may sh|
|00001c20| 61 72 65 20 61 20 72 65 | 66 65 72 65 6e 63 65 20 |are a re|ference |
|00001c30| 74 6f 20 61 20 70 61 72 | 74 20 6f 66 20 61 20 6c |to a par|t of a l|
|00001c40| 61 72 67 65 72 20 73 74 | 72 75 63 74 75 72 65 29 |arger st|ructure)|
|00001c50| 2e 0d 54 68 65 20 6f 6e | 6c 79 20 70 6f 6c 79 6c |..The on|ly polyl|
|00001c60| 69 74 68 69 63 20 73 74 | 72 75 63 74 75 72 65 20 |ithic st|ructure |
|00001c70| 69 6e 20 74 68 65 20 43 | 6f 6c 6c 65 63 74 69 6f |in the C|ollectio|
|00001c80| 6e 73 20 63 6f 6d 70 6f | 6e 65 6e 74 20 69 73 20 |ns compo|nent is |
|00001c90| 74 68 65 20 42 43 5f 54 | 42 69 6e 61 72 79 54 72 |the BC_T|BinaryTr|
|00001ca0| 65 65 20 63 6c 61 73 73 | 2c 20 62 65 63 61 75 73 |ee class|, becaus|
|00001cb0| 65 20 61 6e 20 6f 62 6a | 65 63 74 20 6f 66 20 74 |e an obj|ect of t|
|00001cc0| 68 61 74 20 63 6c 61 73 | 73 20 63 61 6e 20 64 65 |hat clas|s can de|
|00001cd0| 6e 6f 74 65 20 61 20 62 | 72 61 6e 63 68 20 6f 66 |note a b|ranch of|
|00001ce0| 20 61 20 6c 61 72 67 65 | 72 20 74 72 65 65 2e 20 | a large|r tree. |
|00001cf0| 0d 44 79 6e 61 6d 69 63 | 20 61 6e 64 20 75 6e 62 |.Dynamic| and unb|
|00001d00| 6f 75 6e 64 65 64 20 63 | 6f 6e 74 61 69 6e 65 72 |ounded c|ontainer|
|00001d10| 73 0d 4f 6e 65 20 6f 66 | 20 79 6f 75 72 20 6d 6f |s.One of| your mo|
|00001d20| 73 74 20 69 6d 70 6f 72 | 74 61 6e 74 20 64 65 63 |st impor|tant dec|
|00001d30| 69 73 69 6f 6e 73 20 77 | 68 65 6e 20 75 73 69 6e |isions w|hen usin|
|00001d40| 67 20 74 68 65 20 43 6f | 6c 6c 65 63 74 69 6f 6e |g the Co|llection|
|00001d50| 73 20 63 6f 6d 70 6f 6e | 65 6e 74 20 77 69 6c 6c |s compon|ent will|
|00001d60| 20 62 65 20 74 6f 20 63 | 68 6f 6f 73 65 20 74 68 | be to c|hoose th|
|00001d70| 65 20 63 6f 72 72 65 63 | 74 20 63 6f 6e 74 61 69 |e correc|t contai|
|00001d80| 6e 65 72 20 66 6f 72 20 | 79 6f 75 72 20 43 6f 6c |ner for |your Col|
|00001d90| 6c 65 63 74 69 6f 6e 73 | 20 73 74 72 75 63 74 75 |lections| structu|
|00001da0| 72 65 2e 20 54 68 65 20 | 43 6f 6c 6c 65 63 74 69 |re. The |Collecti|
|00001db0| 6f 6e 73 20 63 6f 6d 70 | 6f 6e 65 6e 74 20 61 6c |ons comp|onent al|
|00001dc0| 6c 6f 77 73 20 79 6f 75 | 20 74 6f 20 63 68 6f 6f |lows you| to choo|
|00001dd0| 73 65 20 76 61 72 79 69 | 6e 67 20 74 69 6d 65 20 |se varyi|ng time |
|00001de0| 61 6e 64 20 73 70 61 63 | 65 20 73 65 6d 61 6e 74 |and spac|e semant|
|00001df0| 69 63 73 20 66 72 6f 6d | 20 61 20 73 75 62 73 65 |ics from| a subse|
|00001e00| 74 20 6f 66 20 74 68 65 | 20 66 6f 72 6d 73 20 70 |t of the| forms p|
|00001e10| 72 6f 76 69 64 65 64 20 | 62 79 20 74 68 65 20 42 |rovided |by the B|
|00001e20| 6f 6f 63 68 20 63 6f 6d | 70 6f 6e 65 6e 74 73 2e |ooch com|ponents.|
|00001e30| 20 54 68 65 20 43 6f 6c | 6c 65 63 74 69 6f 6e 73 | The Col|lections|
|00001e40| 20 63 6f 6d 70 6f 6e 65 | 6e 74 20 70 72 6f 76 69 | compone|nt provi|
|00001e50| 64 65 73 20 64 79 6e 61 | 6d 69 63 20 61 6e 64 20 |des dyna|mic and |
|00001e60| 75 6e 62 6f 75 6e 64 65 | 64 20 66 6f 72 6d 73 2c |unbounde|d forms,|
|00001e70| 20 61 73 20 66 6f 6c 6c | 6f 77 73 3a 0d a5 09 44 | as foll|ows:...D|
|00001e80| 79 6e 61 6d 69 63 d1 74 | 68 65 20 73 74 72 75 63 |ynamic.t|he struc|
|00001e90| 74 75 72 65 20 69 73 20 | 73 74 6f 72 65 64 20 6f |ture is |stored o|
|00001ea0| 6e 20 74 68 65 20 68 65 | 61 70 20 61 73 20 61 6e |n the he|ap as an|
|00001eb0| 20 61 72 72 61 79 20 77 | 68 6f 73 65 20 6c 65 6e | array w|hose len|
|00001ec0| 67 74 68 20 6d 61 79 20 | 73 68 72 69 6e 6b 20 6f |gth may |shrink o|
|00001ed0| 72 20 67 72 6f 77 20 69 | 6e 20 6d 75 6c 74 69 70 |r grow i|n multip|
|00001ee0| 6c 65 73 20 6f 66 20 73 | 6f 6d 65 20 63 68 75 6e |les of s|ome chun|
|00001ef0| 6b 20 73 69 7a 65 2e 20 | 54 68 75 73 2c 20 74 68 |k size. |Thus, th|
|00001f00| 65 20 73 74 72 75 63 74 | 75 72 65 20 75 73 65 73 |e struct|ure uses|
|00001f10| 20 73 70 61 63 65 20 65 | 66 66 69 63 69 65 6e 74 | space e|fficient|
|00001f20| 6c 79 2c 20 73 69 6e 63 | 65 20 73 74 6f 72 61 67 |ly, sinc|e storag|
|00001f30| 65 20 69 73 20 61 6c 6c | 6f 63 61 74 65 64 20 66 |e is all|ocated f|
|00001f40| 6f 72 20 61 73 20 6d 61 | 6e 79 20 69 74 65 6d 73 |or as ma|ny items|
|00001f50| 20 61 73 20 6e 65 63 65 | 73 73 61 72 79 2e 0d a5 | as nece|ssary...|
|00001f60| 09 55 6e 62 6f 75 6e 64 | 65 64 d1 74 68 65 20 73 |.Unbound|ed.the s|
|00001f70| 74 72 75 63 74 75 72 65 | 20 69 73 20 73 74 6f 72 |tructure| is stor|
|00001f80| 65 64 20 6f 6e 20 74 68 | 65 20 68 65 61 70 20 61 |ed on th|e heap a|
|00001f90| 6e 64 20 6d 61 79 20 67 | 72 6f 77 20 74 6f 20 74 |nd may g|row to t|
|00001fa0| 68 65 20 6c 69 6d 69 74 | 73 20 6f 66 20 61 76 61 |he limit|s of ava|
|00001fb0| 69 6c 61 62 6c 65 20 6d | 65 6d 6f 72 79 2e 20 54 |ilable m|emory. T|
|00001fc0| 68 65 20 75 6e 62 6f 75 | 6e 64 65 64 20 66 6f 72 |he unbou|nded for|
|00001fd0| 6d 20 64 6f 65 73 20 77 | 61 73 74 65 20 74 69 6d |m does w|aste tim|
|00001fe0| 65 20 66 6f 72 20 73 65 | 71 75 65 6e 63 65 73 2c |e for se|quences,|
|00001ff0| 20 62 65 63 61 75 73 65 | 20 73 65 61 72 63 68 69 | because| searchi|
|00002000| 6e 67 20 66 6f 72 20 61 | 6e 20 69 74 65 6d 20 6f |ng for a|n item o|
|00002010| 72 20 69 6e 73 65 72 74 | 69 6e 67 20 61 6e 20 69 |r insert|ing an i|
|00002020| 74 65 6d 20 69 6e 20 74 | 68 65 20 6d 69 64 64 6c |tem in t|he middl|
|00002030| 65 20 6f 66 20 74 68 65 | 20 73 65 71 75 65 6e 63 |e of the| sequenc|
|00002040| 65 20 6d 61 79 20 72 65 | 71 75 69 72 65 20 74 72 |e may re|quire tr|
|00002050| 61 76 65 72 73 69 6e 67 | 20 69 74 73 20 65 6e 74 |aversing| its ent|
|00002060| 69 72 65 20 73 74 72 75 | 63 74 75 72 65 2e 20 0d |ire stru|cture. .|
|00002070| 4d 6f 72 65 20 64 65 74 | 61 69 6c 73 20 61 62 6f |More det|ails abo|
|00002080| 75 74 20 68 6f 77 20 74 | 6f 20 75 73 65 20 74 68 |ut how t|o use th|
|00002090| 65 73 65 20 63 6f 6e 74 | 61 69 6e 65 72 73 20 61 |ese cont|ainers a|
|000020a0| 72 65 20 67 69 76 65 6e | 20 69 6e 20 74 68 65 20 |re given| in the |
|000020b0| 73 65 63 74 69 6f 6e 20 | d2 55 73 69 6e 67 20 74 |section |.Using t|
|000020c0| 68 65 20 64 79 6e 61 6d | 69 63 20 61 6e 64 20 75 |he dynam|ic and u|
|000020d0| 6e 62 6f 75 6e 64 65 64 | 20 63 6f 6e 74 61 69 6e |nbounded| contain|
|000020e0| 65 72 73 d3 20 6f 6e 20 | 70 61 67 65 20 39 2e 0d |ers. on |page 9..|
|000020f0| 43 6f 6c 6c 65 63 74 69 | 6f 6e 73 20 63 6f 6d 70 |Collecti|ons comp|
|00002100| 6f 6e 65 6e 74 20 64 65 | 73 69 67 6e 0d 54 68 65 |onent de|sign.The|
|00002110| 20 43 6f 6c 6c 65 63 74 | 69 6f 6e 73 20 63 6f 6d | Collect|ions com|
|00002120| 70 6f 6e 65 6e 74 20 77 | 61 73 20 64 65 73 69 67 |ponent w|as desig|
|00002130| 6e 65 64 20 74 6f 20 6d | 65 65 74 20 74 68 65 20 |ned to m|eet the |
|00002140| 66 6f 6c 6c 6f 77 69 6e | 67 20 67 6f 61 6c 73 3a |followin|g goals:|
|00002150| 0d a5 09 43 6f 6d 70 6c | 65 74 65 6e 65 73 73 2e |...Compl|eteness.|
|00002160| 20 54 68 65 20 63 6f 6d | 70 6f 6e 65 6e 74 20 70 | The com|ponent p|
|00002170| 72 6f 76 69 64 65 73 20 | 63 6c 61 73 73 65 73 20 |rovides |classes |
|00002180| 66 6f 72 20 6d 61 6e 79 | 20 62 61 73 69 63 20 64 |for many| basic d|
|00002190| 61 74 61 20 73 74 72 75 | 63 74 75 72 65 73 20 61 |ata stru|ctures a|
|000021a0| 6e 64 20 61 6c 67 6f 72 | 69 74 68 6d 73 2e 20 41 |nd algor|ithms. A|
|000021b0| 64 64 69 74 69 6f 6e 61 | 6c 6c 79 2c 20 66 6f 72 |dditiona|lly, for|
|000021c0| 20 65 61 63 68 20 6b 69 | 6e 64 20 6f 66 20 73 74 | each ki|nd of st|
|000021d0| 72 75 63 74 75 72 65 2c | 20 74 68 65 20 63 6f 6d |ructure,| the com|
|000021e0| 70 6f 6e 65 6e 74 20 70 | 72 6f 76 69 64 65 73 20 |ponent p|rovides |
|000021f0| 61 20 66 61 6d 69 6c 79 | 20 6f 66 20 63 6c 61 73 |a family| of clas|
|00002200| 73 65 73 2c 20 75 6e 69 | 74 65 64 20 62 79 20 61 |ses, uni|ted by a|
|00002210| 20 73 68 61 72 65 64 20 | 69 6e 74 65 72 66 61 63 | shared |interfac|
|00002220| 65 20 62 75 74 20 65 61 | 63 68 20 65 6d 70 6c 6f |e but ea|ch emplo|
|00002230| 79 69 6e 67 20 61 20 64 | 69 66 66 65 72 65 6e 74 |ying a d|ifferent|
|00002240| 20 72 65 70 72 65 73 65 | 6e 74 61 74 69 6f 6e 2e | represe|ntation.|
|00002250| 20 54 68 75 73 2c 20 79 | 6f 75 20 63 61 6e 20 73 | Thus, y|ou can s|
|00002260| 65 6c 65 63 74 20 74 68 | 65 20 63 6c 61 73 73 20 |elect th|e class |
|00002270| 77 69 74 68 20 74 68 65 | 20 74 69 6d 65 20 61 6e |with the| time an|
|00002280| 64 20 73 70 61 63 65 20 | 73 65 6d 61 6e 74 69 63 |d space |semantic|
|00002290| 73 20 6d 6f 73 74 20 61 | 70 70 72 6f 70 72 69 61 |s most a|ppropria|
|000022a0| 74 65 20 74 6f 20 79 6f | 75 72 20 61 70 70 6c 69 |te to yo|ur appli|
|000022b0| 63 61 74 69 6f 6e 2e 0d | a5 09 41 64 61 70 74 61 |cation..|..Adapta|
|000022c0| 62 69 6c 69 74 79 2e 20 | 54 68 65 20 63 6f 6d 70 |bility. |The comp|
|000022d0| 6f 6e 65 6e 74 d5 73 20 | 70 6c 61 74 66 6f 72 6d |onent.s |platform|
|000022e0| 2d 73 70 65 63 69 66 69 | 63 20 61 73 70 65 63 74 |-specifi|c aspect|
|000022f0| 73 20 61 72 65 20 69 64 | 65 6e 74 69 66 69 65 64 |s are id|entified|
|00002300| 20 61 6e 64 20 69 73 6f | 6c 61 74 65 64 20 75 73 | and iso|lated us|
|00002310| 69 6e 67 20 74 65 6d 70 | 6c 61 74 65 20 61 72 67 |ing temp|late arg|
|00002320| 75 6d 65 6e 74 73 2c 20 | 73 6f 20 74 68 61 74 20 |uments, |so that |
|00002330| 79 6f 75 20 6d 61 79 20 | 6d 61 6b 65 20 6c 6f 63 |you may |make loc|
|00002340| 61 6c 20 73 75 62 73 74 | 69 74 75 74 69 6f 6e 73 |al subst|itutions|
|00002350| 2e 20 49 6e 20 70 61 72 | 74 69 63 75 6c 61 72 2c |. In par|ticular,|
|00002360| 20 79 6f 75 20 68 61 76 | 65 20 63 6f 6e 74 72 6f | you hav|e contro|
|00002370| 6c 20 6f 76 65 72 20 73 | 74 6f 72 61 67 65 20 6d |l over s|torage m|
|00002380| 61 6e 61 67 65 6d 65 6e | 74 20 70 6f 6c 69 63 69 |anagemen|t polici|
|00002390| 65 73 2e 0d a5 09 45 66 | 66 69 63 69 65 6e 63 79 |es....Ef|ficiency|
|000023a0| 2e 20 54 68 65 20 63 6f | 6d 70 6f 6e 65 6e 74 20 |. The co|mponent |
|000023b0| 70 72 6f 76 69 64 65 73 | 20 65 61 73 69 6c 79 20 |provides| easily |
|000023c0| 61 73 73 65 6d 62 6c 65 | 64 20 6d 65 63 68 61 6e |assemble|d mechan|
|000023d0| 69 73 6d 73 20 28 65 66 | 66 69 63 69 65 6e 74 20 |isms (ef|ficient |
|000023e0| 69 6e 20 63 6f 6d 70 69 | 6c 61 74 69 6f 6e 20 72 |in compi|lation r|
|000023f0| 65 73 6f 75 72 63 65 73 | 29 20 74 68 61 74 20 69 |esources|) that i|
|00002400| 6d 70 6f 73 65 20 6d 69 | 6e 69 6d 61 6c 20 72 75 |mpose mi|nimal ru|
|00002410| 6e 20 74 69 6d 65 20 61 | 6e 64 20 6d 65 6d 6f 72 |n time a|nd memor|
|00002420| 79 20 6f 76 65 72 68 65 | 61 64 20 28 65 66 66 69 |y overhe|ad (effi|
|00002430| 63 69 65 6e 74 20 69 6e | 20 65 78 65 63 75 74 69 |cient in| executi|
|00002440| 6f 6e 20 72 65 73 6f 75 | 72 63 65 73 29 20 61 6e |on resou|rces) an|
|00002450| 64 20 74 68 61 74 20 61 | 72 65 20 6d 6f 72 65 20 |d that a|re more |
|00002460| 72 65 6c 69 61 62 6c 65 | 20 74 68 61 6e 20 68 61 |reliable| than ha|
|00002470| 6e 64 2d 62 75 69 6c 74 | 20 6d 65 63 68 61 6e 69 |nd-built| mechani|
|00002480| 73 6d 73 20 28 65 66 66 | 69 63 69 65 6e 74 20 69 |sms (eff|icient i|
|00002490| 6e 20 79 6f 75 72 20 72 | 65 73 6f 75 72 63 65 73 |n your r|esources|
|000024a0| 29 2e 0d a5 09 53 61 66 | 65 74 79 2e 20 45 61 63 |)....Saf|ety. Eac|
|000024b0| 68 20 63 6c 61 73 73 20 | 6f 66 20 74 68 65 20 63 |h class |of the c|
|000024c0| 6f 6d 70 6f 6e 65 6e 74 | 20 69 73 20 64 65 73 69 |omponent| is desi|
|000024d0| 67 6e 65 64 20 74 6f 20 | 62 65 20 74 79 70 65 2d |gned to |be type-|
|000024e0| 73 61 66 65 2c 20 73 6f | 20 74 68 61 74 20 73 74 |safe, so| that st|
|000024f0| 61 74 69 63 20 61 73 73 | 75 6d 70 74 69 6f 6e 73 |atic ass|umptions|
|00002500| 20 61 62 6f 75 74 20 74 | 68 65 20 62 65 68 61 76 | about t|he behav|
|00002510| 69 6f 72 20 6f 66 20 61 | 20 63 6c 61 73 73 20 61 |ior of a| class a|
|00002520| 72 65 20 65 6e 66 6f 72 | 63 65 64 20 62 79 20 74 |re enfor|ced by t|
|00002530| 68 65 20 63 6f 6d 70 69 | 6c 65 72 2e 20 41 64 64 |he compi|ler. Add|
|00002540| 69 74 69 6f 6e 61 6c 6c | 79 2c 20 65 78 63 65 70 |itionall|y, excep|
|00002550| 74 69 6f 6e 73 20 69 64 | 65 6e 74 69 66 79 20 63 |tions id|entify c|
|00002560| 6f 6e 64 69 74 69 6f 6e | 73 20 75 6e 64 65 72 20 |ondition|s under |
|00002570| 77 68 69 63 68 20 61 20 | 63 6c 61 73 73 d5 73 20 |which a |class.s |
|00002580| 64 79 6e 61 6d 69 63 20 | 73 65 6d 61 6e 74 69 63 |dynamic |semantic|
|00002590| 73 20 61 72 65 20 76 69 | 6f 6c 61 74 65 64 2c 20 |s are vi|olated, |
|000025a0| 62 75 74 20 77 69 74 68 | 6f 75 74 20 63 6f 72 72 |but with|out corr|
|000025b0| 75 70 74 69 6e 67 20 74 | 68 65 20 73 74 61 74 65 |upting t|he state|
|000025c0| 20 6f 66 20 74 68 65 20 | 6f 62 6a 65 63 74 20 74 | of the |object t|
|000025d0| 68 61 74 20 74 68 72 65 | 77 20 74 68 65 20 65 78 |hat thre|w the ex|
|000025e0| 63 65 70 74 69 6f 6e 2e | 0d a5 09 45 61 73 65 20 |ception.|...Ease |
|000025f0| 6f 66 20 75 73 65 2e 20 | 41 20 63 6c 65 61 72 20 |of use. |A clear |
|00002600| 6f 72 67 61 6e 69 7a 61 | 74 69 6f 6e 20 61 6c 6c |organiza|tion all|
|00002610| 6f 77 73 20 79 6f 75 20 | 74 6f 20 73 65 6c 65 63 |ows you |to selec|
|00002620| 74 20 61 70 70 72 6f 70 | 72 69 61 74 65 20 66 6f |t approp|riate fo|
|00002630| 72 6d 73 20 6f 66 20 65 | 61 63 68 20 73 74 72 75 |rms of e|ach stru|
|00002640| 63 74 75 72 65 20 61 6e | 64 20 74 6f 6f 6c 2e 0d |cture an|d tool..|
|00002650| a5 09 45 78 74 65 6e 73 | 69 62 69 6c 69 74 79 2e |..Extens|ibility.|
|00002660| 20 59 6f 75 20 63 61 6e | 20 61 64 64 20 6e 65 77 | You can| add new|
|00002670| 20 64 61 74 61 20 73 74 | 72 75 63 74 75 72 65 73 | data st|ructures|
|00002680| 20 61 6e 64 20 61 6c 67 | 6f 72 69 74 68 6d 73 20 | and alg|orithms |
|00002690| 61 6e 64 20 73 74 69 6c | 6c 20 70 72 65 73 65 72 |and stil|l preser|
|000026a0| 76 65 20 74 68 65 20 61 | 72 63 68 69 74 65 63 74 |ve the a|rchitect|
|000026b0| 75 72 61 6c 20 69 6e 74 | 65 67 72 69 74 79 20 6f |ural int|egrity o|
|000026c0| 66 20 74 68 65 20 63 6f | 6d 70 6f 6e 65 6e 74 2e |f the co|mponent.|
|000026d0| 0d 41 64 64 69 74 69 6f | 6e 61 6c 20 43 6f 6c 6c |.Additio|nal Coll|
|000026e0| 65 63 74 69 6f 6e 73 20 | 63 6f 6d 70 6f 6e 65 6e |ections |componen|
|000026f0| 74 20 69 6e 74 65 72 66 | 61 63 65 73 0d 54 68 65 |t interf|aces.The|
|00002700| 20 66 6f 6c 6c 6f 77 69 | 6e 67 20 6e 61 6d 65 64 | followi|ng named|
|00002710| 20 74 79 70 65 73 20 61 | 72 65 20 75 73 65 64 20 | types a|re used |
|00002720| 74 68 72 6f 75 67 68 6f | 75 74 20 74 68 65 20 6c |througho|ut the l|
|00002730| 69 62 72 61 72 79 3a 0d | a5 09 42 43 5f 49 6e 64 |ibrary:.|..BC_Ind|
|00002740| 65 78 3b 20 64 65 6e 6f | 74 65 73 20 61 6e 20 69 |ex; deno|tes an i|
|00002750| 6e 64 65 78 20 69 6e 74 | 6f 20 61 20 73 74 72 75 |ndex int|o a stru|
|00002760| 63 74 75 72 65 2c 20 77 | 69 74 68 20 61 20 72 61 |cture, w|ith a ra|
|00002770| 6e 67 65 20 66 72 6f 6d | 20 30 20 74 6f 20 6e 2e |nge from| 0 to n.|
|00002780| 0d a5 09 42 43 5f 45 78 | 74 65 6e 64 65 64 49 6e |...BC_Ex|tendedIn|
|00002790| 64 65 78 3b 20 64 65 6e | 6f 74 65 73 20 61 6e 20 |dex; den|otes an |
|000027a0| 69 6e 64 65 78 20 69 6e | 74 6f 20 61 20 73 74 72 |index in|to a str|
|000027b0| 75 63 74 75 72 65 2c 20 | 77 69 74 68 20 61 20 72 |ucture, |with a r|
|000027c0| 61 6e 67 65 20 66 72 6f | 6d 20 2d 31 20 74 6f 20 |ange fro|m -1 to |
|000027d0| 6e 2e 20 42 79 20 63 6f | 6e 76 65 6e 74 69 6f 6e |n. By co|nvention|
|000027e0| 2c 20 61 20 76 61 6c 75 | 65 20 6f 66 20 2d 31 20 |, a valu|e of -1 |
|000027f0| 64 65 6e 6f 74 65 73 20 | 61 20 6c 6f 63 61 74 69 |denotes |a locati|
|00002800| 6f 6e 20 6f 75 74 73 69 | 64 65 20 6f 66 20 74 68 |on outsi|de of th|
|00002810| 65 20 73 74 72 75 63 74 | 75 72 65 2e 0d a5 09 42 |e struct|ure....B|
|00002820| 43 5f 42 6f 6f 6c 65 61 | 6e 3b 20 64 65 6e 6f 74 |C_Boolea|n; denot|
|00002830| 65 73 20 61 20 62 6f 6f | 6c 65 61 6e 20 76 61 6c |es a boo|lean val|
|00002840| 75 65 2e 20 42 79 20 63 | 6f 6e 76 65 6e 74 69 6f |ue. By c|onventio|
|00002850| 6e 2c 20 61 20 76 61 6c | 75 65 20 6f 66 20 30 20 |n, a val|ue of 0 |
|00002860| 64 65 6e 6f 74 65 73 20 | 66 61 6c 73 65 2c 20 61 |denotes |false, a|
|00002870| 6e 64 20 61 6e 79 20 6f | 74 68 65 72 20 76 61 6c |nd any o|ther val|
|00002880| 75 65 20 28 75 73 75 61 | 6c 6c 79 20 31 29 20 64 |ue (usua|lly 1) d|
|00002890| 65 6e 6f 74 65 73 20 74 | 72 75 65 2e 0d 43 6f 6d |enotes t|rue..Com|
|000028a0| 70 6f 6e 65 6e 74 20 64 | 65 70 65 6e 64 65 6e 63 |ponent d|ependenc|
|000028b0| 69 65 73 0d 57 68 65 6e | 20 61 20 63 6f 6c 6c 65 |ies.When| a colle|
|000028c0| 63 74 69 6f 6e 73 20 73 | 74 72 75 63 74 75 72 65 |ctions s|tructure|
|000028d0| 20 75 73 65 73 20 74 68 | 65 20 75 6e 6d 61 6e 61 | uses th|e unmana|
|000028e0| 67 65 64 20 73 74 79 6c | 65 20 6f 66 20 6d 61 6e |ged styl|e of man|
|000028f0| 61 67 69 6e 67 20 73 74 | 6f 72 61 67 65 20 28 73 |aging st|orage (s|
|00002900| 65 65 20 d2 4d 61 6e 61 | 67 69 6e 67 20 73 74 6f |ee .Mana|ging sto|
|00002910| 72 61 67 65 d3 20 6f 6e | 20 70 61 67 65 20 31 32 |rage. on| page 12|
|00002920| 29 2c 20 74 68 65 20 73 | 74 72 75 63 74 75 72 65 |), the s|tructure|
|00002930| 20 64 65 70 65 6e 64 73 | 20 75 70 6f 6e 20 74 68 | depends| upon th|
|00002940| 65 20 69 6d 70 6c 65 6d | 65 6e 74 61 74 69 6f 6e |e implem|entation|
|00002950| 20 6f 66 20 6f 70 65 72 | 61 74 6f 72 20 6e 65 77 | of oper|ator new|
|00002960| 20 61 6e 64 20 6f 70 65 | 72 61 74 6f 72 20 64 65 | and ope|rator de|
|00002970| 6c 65 74 65 2e 20 54 68 | 65 20 4f 70 65 6e 44 6f |lete. Th|e OpenDo|
|00002980| 63 20 6d 65 6d 6f 72 79 | 20 6d 61 6e 61 67 65 72 |c memory| manager|
|00002990| 20 70 72 6f 76 69 64 65 | 73 20 61 6e 20 69 6d 70 | provide|s an imp|
|000029a0| 6c 65 6d 65 6e 74 61 74 | 69 6f 6e 20 6f 66 20 74 |lementat|ion of t|
|000029b0| 68 6f 73 65 20 6f 70 65 | 72 61 74 6f 72 73 2e 20 |hose ope|rators. |
|000029c0| 48 6f 77 65 76 65 72 2c | 20 62 65 63 61 75 73 65 |However,| because|
|000029d0| 20 74 68 65 20 43 6f 6c | 6c 65 63 74 69 6f 6e 73 | the Col|lections|
|000029e0| 20 63 6f 6d 70 6f 6e 65 | 6e 74 20 77 69 6c 6c 20 | compone|nt will |
|000029f0| 75 73 65 20 77 68 61 74 | 65 76 65 72 20 69 6d 70 |use what|ever imp|
|00002a00| 6c 65 6d 65 6e 74 61 74 | 69 6f 6e 73 20 6f 66 20 |lementat|ions of |
|00002a10| 6e 65 77 20 61 6e 64 20 | 64 65 6c 65 74 65 20 61 |new and |delete a|
|00002a20| 72 65 20 70 72 65 73 65 | 6e 74 2c 20 74 68 65 20 |re prese|nt, the |
|00002a30| 43 6f 6c 6c 65 63 74 69 | 6f 6e 73 20 63 6f 6d 70 |Collecti|ons comp|
|00002a40| 6f 6e 65 6e 74 20 64 6f | 65 73 20 6e 6f 74 20 64 |onent do|es not d|
|00002a50| 65 70 65 6e 64 20 6f 6e | 20 74 68 65 20 4f 70 65 |epend on| the Ope|
|00002a60| 6e 44 6f 63 20 6d 65 6d | 6f 72 79 20 6d 61 6e 61 |nDoc mem|ory mana|
|00002a70| 67 65 72 2e 0d 4f 74 68 | 65 72 20 74 68 61 6e 20 |ger..Oth|er than |
|00002a80| 74 68 65 20 75 73 65 20 | 6f 66 20 74 68 65 20 4f |the use |of the O|
|00002a90| 70 65 6e 44 6f 63 20 6d | 65 6d 6f 72 79 20 6d 61 |penDoc m|emory ma|
|00002aa0| 6e 61 67 65 72 20 69 66 | 20 61 76 61 69 6c 61 62 |nager if| availab|
|00002ab0| 6c 65 2c 20 74 68 65 20 | 43 6f 6c 6c 65 63 74 69 |le, the |Collecti|
|00002ac0| 6f 6e 73 20 63 6f 6d 70 | 6f 6e 65 6e 74 20 64 6f |ons comp|onent do|
|00002ad0| 65 73 20 6e 6f 74 20 64 | 65 70 65 6e 64 20 6f 6e |es not d|epend on|
|00002ae0| 20 61 6e 79 20 6f 74 68 | 65 72 20 4f 50 46 20 63 | any oth|er OPF c|
|00002af0| 6f 6d 70 6f 6e 65 6e 74 | 2e 0d 55 73 69 6e 67 20 |omponent|..Using |
|00002b00| 74 68 65 20 43 6f 6c 6c | 65 63 74 69 6f 6e 73 20 |the Coll|ections |
|00002b10| 43 6f 6d 70 6f 6e 65 6e | 74 0d 41 6c 74 68 6f 75 |Componen|t.Althou|
|00002b20| 67 68 20 79 6f 75 20 63 | 61 6e 20 73 75 62 63 6c |gh you c|an subcl|
|00002b30| 61 73 73 20 74 68 65 20 | 63 6c 61 73 73 65 73 20 |ass the |classes |
|00002b40| 6f 66 20 74 68 65 20 43 | 6f 6c 6c 65 63 74 69 6f |of the C|ollectio|
|00002b50| 6e 73 20 63 6f 6d 70 6f | 6e 65 6e 74 2c 20 74 68 |ns compo|nent, th|
|00002b60| 61 74 20 69 73 20 6e 6f | 74 20 74 68 65 20 69 6e |at is no|t the in|
|00002b70| 74 65 6e 74 69 6f 6e 20 | 6f 66 20 69 74 73 20 64 |tention |of its d|
|00002b80| 65 73 69 67 6e 2e 20 49 | 6e 73 74 65 61 64 2c 20 |esign. I|nstead, |
|00002b90| 79 6f 75 20 77 69 6c 6c | 20 74 79 70 69 63 61 6c |you will| typical|
|00002ba0| 6c 79 20 62 65 20 69 6e | 73 74 61 6e 74 69 61 74 |ly be in|stantiat|
|00002bb0| 69 6e 67 20 66 72 6f 6d | 20 74 68 65 20 63 6c 61 |ing from| the cla|
|00002bc0| 73 73 20 74 65 6d 70 6c | 61 74 65 73 20 70 72 6f |ss templ|ates pro|
|00002bd0| 76 69 64 65 64 20 62 79 | 20 74 68 65 20 63 6f 6d |vided by| the com|
|00002be0| 70 6f 6e 65 6e 74 2c 20 | 61 73 20 64 69 73 63 75 |ponent, |as discu|
|00002bf0| 73 73 65 64 20 69 6e 20 | 74 68 65 20 6e 65 78 74 |ssed in |the next|
|00002c00| 20 73 65 63 74 69 6f 6e | 2e 20 0d 49 6e 73 74 61 | section|. .Insta|
|00002c10| 6e 74 69 61 74 69 6e 67 | 20 77 69 74 68 69 6e 20 |ntiating| within |
|00002c20| 74 68 65 20 43 6f 6c 6c | 65 63 74 69 6f 6e 73 20 |the Coll|ections |
|00002c30| 63 6f 6d 70 6f 6e 65 6e | 74 0d 54 68 65 20 43 6f |componen|t.The Co|
|00002c40| 6c 6c 65 63 74 69 6f 6e | 73 20 63 6f 6d 70 6f 6e |llection|s compon|
|00002c50| 65 6e 74 20 61 6c 6c 6f | 77 73 20 79 6f 75 20 74 |ent allo|ws you t|
|00002c60| 6f 20 75 73 65 20 74 68 | 65 20 43 2b 2b 20 74 65 |o use th|e C++ te|
|00002c70| 6d 70 6c 61 74 65 20 66 | 65 61 74 75 72 65 20 74 |mplate f|eature t|
|00002c80| 6f 20 70 61 72 61 6d 65 | 74 65 72 69 7a 65 20 65 |o parame|terize e|
|00002c90| 61 63 68 20 73 74 72 75 | 63 74 75 72 65 20 77 69 |ach stru|cture wi|
|00002ca0| 74 68 20 74 68 65 20 6b | 69 6e 64 20 6f 66 20 69 |th the k|ind of i|
|00002cb0| 74 65 6d 20 69 74 20 63 | 6f 6e 74 61 69 6e 73 2e |tem it c|ontains.|
|00002cc0| 20 59 6f 75 20 6e 6f 72 | 6d 61 6c 6c 79 20 69 6e | You nor|mally in|
|00002cd0| 73 74 61 6e 74 69 61 74 | 65 20 61 20 63 6c 61 73 |stantiat|e a clas|
|00002ce0| 73 20 66 72 6f 6d 20 6f | 6e 65 20 6f 66 20 74 68 |s from o|ne of th|
|00002cf0| 65 20 73 75 62 63 6c 61 | 73 73 65 73 20 6f 66 20 |e subcla|sses of |
|00002d00| 74 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 6b 69 |the foll|owing ki|
|00002d10| 6e 64 73 20 6f 66 20 63 | 6c 61 73 73 20 74 65 6d |nds of c|lass tem|
|00002d20| 70 6c 61 74 65 73 3a 0d | a5 09 42 69 6e 61 72 79 |plates:.|..Binary|
|00002d30| 20 74 72 65 65 73 3a 20 | 43 6f 6e 63 72 65 74 65 | trees: |Concrete|
|00002d40| 20 63 6c 61 73 73 20 42 | 43 5f 54 42 69 6e 61 72 | class B|C_TBinar|
|00002d50| 79 54 72 65 65 20 28 70 | 61 67 65 20 33 35 29 0d |yTree (p|age 35).|
|00002d60| a5 09 43 6f 6c 6c 65 63 | 74 69 6f 6e 73 3a 20 42 |..Collec|tions: B|
|00002d70| 61 73 65 20 63 6c 61 73 | 73 20 42 43 5f 54 43 6f |ase clas|s BC_TCo|
|00002d80| 6c 6c 65 63 74 69 6f 6e | 20 28 70 61 67 65 20 34 |llection| (page 4|
|00002d90| 33 29 0d a5 09 4d 61 70 | 73 3a 20 42 61 73 65 20 |3)...Map|s: Base |
|00002da0| 63 6c 61 73 73 20 42 43 | 5f 54 4d 61 70 20 28 70 |class BC|_TMap (p|
|00002db0| 61 67 65 20 39 39 29 0d | a5 09 51 75 65 75 65 73 |age 99).|..Queues|
|00002dc0| 3a 20 42 61 73 65 20 63 | 6c 61 73 73 20 42 43 5f |: Base c|lass BC_|
|00002dd0| 54 51 75 65 75 65 20 28 | 70 61 67 65 20 31 32 39 |TQueue (|page 129|
|00002de0| 29 0d a5 09 53 65 74 73 | 3a 20 42 61 73 65 20 63 |)...Sets|: Base c|
|00002df0| 6c 61 73 73 20 42 43 5f | 54 53 65 74 20 28 70 61 |lass BC_|TSet (pa|
|00002e00| 67 65 20 31 35 35 29 0d | a5 09 53 74 61 63 6b 73 |ge 155).|..Stacks|
|00002e10| 3a 20 42 61 73 65 20 63 | 6c 61 73 73 20 42 43 5f |: Base c|lass BC_|
|00002e20| 54 53 74 61 63 6b 20 28 | 70 61 67 65 20 31 37 33 |TStack (|page 173|
|00002e30| 29 0d 53 75 62 63 6c 61 | 73 73 69 6e 67 20 77 69 |).Subcla|ssing wi|
|00002e40| 74 68 69 6e 20 74 68 65 | 20 43 6f 6c 6c 65 63 74 |thin the| Collect|
|00002e50| 69 6f 6e 73 20 63 6f 6d | 70 6f 6e 65 6e 74 0d 59 |ions com|ponent.Y|
|00002e60| 6f 75 20 6e 6f 72 6d 61 | 6c 6c 79 20 64 6f 6e d5 |ou norma|lly don.|
|00002e70| 74 20 73 75 62 63 6c 61 | 73 73 20 74 68 65 20 63 |t subcla|ss the c|
|00002e80| 6c 61 73 73 65 73 20 70 | 72 6f 76 69 64 65 64 20 |lasses p|rovided |
|00002e90| 62 79 20 74 68 65 20 43 | 6f 6c 6c 65 63 74 69 6f |by the C|ollectio|
|00002ea0| 6e 73 20 63 6f 6d 70 6f | 6e 65 6e 74 2e 0d 45 78 |ns compo|nent..Ex|
|00002eb0| 74 65 6e 64 69 6e 67 20 | 74 68 65 20 43 6f 6c 6c |tending |the Coll|
|00002ec0| 65 63 74 69 6f 6e 73 20 | 63 6f 6d 70 6f 6e 65 6e |ections |componen|
|00002ed0| 74 0d 54 68 65 72 65 20 | 61 72 65 20 73 65 76 65 |t.There |are seve|
|00002ee0| 72 61 6c 20 77 61 79 73 | 20 79 6f 75 20 63 61 6e |ral ways| you can|
|00002ef0| 20 65 78 74 65 6e 64 20 | 74 68 65 20 43 6f 6c 6c | extend |the Coll|
|00002f00| 65 63 74 69 6f 6e 73 20 | 63 6f 6d 70 6f 6e 65 6e |ections |componen|
|00002f10| 74 20 74 6f 20 6d 65 65 | 74 20 79 6f 75 72 20 6e |t to mee|t your n|
|00002f20| 65 65 64 73 2c 20 61 73 | 20 64 65 73 63 72 69 62 |eeds, as| describ|
|00002f30| 65 64 20 69 6e 20 74 68 | 65 20 66 6f 6c 6c 6f 77 |ed in th|e follow|
|00002f40| 69 6e 67 20 73 65 63 74 | 69 6f 6e 73 2e 0d 42 75 |ing sect|ions..Bu|
|00002f50| 79 20 6f 74 68 65 72 20 | 42 6f 6f 63 68 20 63 6f |y other |Booch co|
|00002f60| 6d 70 6f 6e 65 6e 74 73 | 0d 54 68 65 20 4f 50 46 |mponents|.The OPF|
|00002f70| 20 43 6f 6c 6c 65 63 74 | 69 6f 6e 73 20 63 6f 6d | Collect|ions com|
|00002f80| 70 6f 6e 65 6e 74 20 69 | 73 20 61 20 73 75 62 73 |ponent i|s a subs|
|00002f90| 65 74 20 6f 66 20 74 68 | 65 20 43 2b 2b 20 42 6f |et of th|e C++ Bo|
|00002fa0| 6f 63 68 20 43 6f 6d 70 | 6f 6e 65 6e 74 73 a8 20 |och Comp|onents. |
|00002fb0| 61 76 61 69 6c 61 62 6c | 65 20 66 72 6f 6d 20 52 |availabl|e from R|
|00002fc0| 61 74 69 6f 6e 61 6c a8 | 2e 20 59 6f 75 20 63 61 |ational.|. You ca|
|00002fd0| 6e 20 70 75 72 63 68 61 | 73 65 20 6f 74 68 65 72 |n purcha|se other|
|00002fe0| 20 63 6f 6c 6c 65 63 74 | 69 6f 6e 73 20 73 74 72 | collect|ions str|
|00002ff0| 75 63 74 75 72 65 73 20 | 61 6e 64 20 74 6f 6f 6c |uctures |and tool|
|00003000| 73 20 66 72 6f 6d 20 52 | 61 74 69 6f 6e 61 6c 2e |s from R|ational.|
|00003010| 0d 41 64 64 20 79 6f 75 | 72 20 6f 77 6e 20 73 74 |.Add you|r own st|
|00003020| 6f 72 61 67 65 20 6d 61 | 6e 61 67 65 72 0d 59 6f |orage ma|nager.Yo|
|00003030| 75 20 63 61 6e 20 69 6e | 73 65 72 74 20 79 6f 75 |u can in|sert you|
|00003040| 72 20 6f 77 6e 20 73 74 | 6f 72 61 67 65 20 6d 61 |r own st|orage ma|
|00003050| 6e 61 67 65 6d 65 6e 74 | 20 70 6f 6c 69 63 79 20 |nagement| policy |
|00003060| 77 69 74 68 6f 75 74 20 | 63 68 61 6e 67 69 6e 67 |without |changing|
|00003070| 20 74 68 65 20 6c 69 62 | 72 61 72 79 2e 20 54 68 | the lib|rary. Th|
|00003080| 65 20 6f 6e 6c 79 20 72 | 65 71 75 69 72 65 6d 65 |e only r|equireme|
|00003090| 6e 74 20 70 6c 61 63 65 | 64 20 75 70 6f 6e 20 61 |nt place|d upon a|
|000030a0| 20 73 74 6f 72 61 67 65 | 20 6d 61 6e 61 67 65 72 | storage| manager|
|000030b0| 20 69 73 20 74 68 61 74 | 20 69 74 20 6d 75 73 74 | is that| it must|
|000030c0| 20 65 78 70 6f 72 74 20 | 74 68 65 20 41 6c 6c 6f | export |the Allo|
|000030d0| 63 61 74 65 20 61 6e 64 | 20 44 65 61 6c 6c 6f 63 |cate and| Dealloc|
|000030e0| 61 74 65 20 6d 65 74 68 | 6f 64 73 2c 20 77 68 69 |ate meth|ods, whi|
|000030f0| 63 68 20 64 69 73 70 65 | 6e 73 65 20 61 6e 64 20 |ch dispe|nse and |
|00003100| 72 65 6c 65 61 73 65 20 | 6d 65 6d 6f 72 79 2c 20 |release |memory, |
|00003110| 72 65 73 70 65 63 74 69 | 76 65 6c 79 2e 0d 55 73 |respecti|vely..Us|
|00003120| 69 6e 67 20 74 68 65 20 | 64 79 6e 61 6d 69 63 20 |ing the |dynamic |
|00003130| 61 6e 64 20 75 6e 62 6f | 75 6e 64 65 64 20 63 6f |and unbo|unded co|
|00003140| 6e 74 61 69 6e 65 72 73 | 0d 54 6f 20 62 65 20 70 |ntainers|.To be p|
|00003150| 72 65 63 69 73 65 2c 20 | 65 61 63 68 20 6f 66 20 |recise, |each of |
|00003160| 74 68 65 73 65 20 74 77 | 6f 20 66 6f 72 6d 73 20 |these tw|o forms |
|00003170| 65 78 68 69 62 69 74 20 | 74 68 65 20 66 6f 6c 6c |exhibit |the foll|
|00003180| 6f 77 69 6e 67 20 73 70 | 61 63 65 20 63 6f 6d 70 |owing sp|ace comp|
|00003190| 6c 65 78 69 74 79 3a 0d | a5 09 44 79 6e 61 6d 69 |lexity:.|..Dynami|
|000031a0| 63 3b 20 09 09 4f 28 6e | 20 2a 20 73 69 7a 65 5f |c; ..O(n| * size_|
|000031b0| 6f 66 28 69 74 65 6d 29 | 29 2c 20 77 68 65 72 65 |of(item)|), where|
|000031c0| 20 6e 20 69 73 20 61 20 | 6d 75 6c 74 69 70 6c 65 | n is a |multiple|
|000031d0| 20 6f 66 20 61 20 09 09 | 63 68 75 6e 6b 20 73 69 | of a ..|chunk si|
|000031e0| 7a 65 2c 20 70 72 6f 76 | 69 64 65 64 20 75 70 6f |ze, prov|ided upo|
|000031f0| 6e 20 74 65 6d 70 6c 61 | 74 65 20 69 6e 73 74 61 |n templa|te insta|
|00003200| 6e 74 69 61 74 69 6f 6e | 0d a5 09 55 6e 62 6f 75 |ntiation|...Unbou|
|00003210| 6e 64 65 64 09 3b 20 4f | 28 6e 20 2a 20 28 73 69 |nded.; O|(n * (si|
|00003220| 7a 65 5f 6f 66 28 69 74 | 65 6d 29 20 2b 20 32 20 |ze_of(it|em) + 2 |
|00003230| 2a 20 73 69 7a 65 5f 6f | 66 28 76 6f 69 64 2a 29 |* size_o|f(void*)|
|00003240| 29 29 0d 54 68 65 20 67 | 75 69 64 65 6c 69 6e 65 |)).The g|uideline|
|00003250| 73 20 69 6e 20 74 68 65 | 20 66 6f 6c 6c 6f 77 69 |s in the| followi|
|00003260| 6e 67 20 73 65 63 74 69 | 6f 6e 73 20 77 69 6c 6c |ng secti|ons will|
|00003270| 20 68 65 6c 70 20 79 6f | 75 20 73 65 6c 65 63 74 | help yo|u select|
|00003280| 20 6f 6e 65 20 6f 66 20 | 74 68 65 73 65 20 63 6f | one of |these co|
|00003290| 6e 63 72 65 74 65 20 66 | 6f 72 6d 73 2e 0d 44 79 |ncrete f|orms..Dy|
|000032a0| 6e 61 6d 69 63 20 63 6f | 6e 74 61 69 6e 65 72 73 |namic co|ntainers|
|000032b0| 0d 54 68 65 20 64 79 6e | 61 6d 69 63 20 63 6f 6e |.The dyn|amic con|
|000032c0| 74 61 69 6e 65 72 20 69 | 73 20 75 73 75 61 6c 6c |tainer i|s usuall|
|000032d0| 79 20 74 68 65 20 6d 6f | 73 74 20 6f 70 74 69 6d |y the mo|st optim|
|000032e0| 61 6c 20 66 6f 72 6d 20 | 66 6f 72 20 6d 6f 73 74 |al form |for most|
|000032f0| 20 73 74 72 75 63 74 75 | 72 65 73 2c 20 61 6c 74 | structu|res, alt|
|00003300| 68 6f 75 67 68 20 61 76 | 65 72 61 67 65 20 6c 65 |hough av|erage le|
|00003310| 6e 67 74 68 20 6f 66 20 | 65 61 63 68 20 69 6e 73 |ngth of |each ins|
|00003320| 74 61 6e 63 65 20 6d 75 | 73 74 20 62 65 20 63 6f |tance mu|st be co|
|00003330| 6e 73 69 64 65 72 65 64 | 20 77 68 65 6e 20 73 65 |nsidered| when se|
|00003340| 74 74 69 6e 67 20 69 74 | 73 20 63 68 75 6e 6b 20 |tting it|s chunk |
|00003350| 73 69 7a 65 2e 20 48 6f | 77 65 76 65 72 2c 20 69 |size. Ho|wever, i|
|00003360| 6e 73 65 72 74 69 6f 6e | 20 6f 74 68 65 72 20 74 |nsertion| other t|
|00003370| 68 61 6e 20 61 74 20 74 | 68 65 20 66 72 6f 6e 74 |han at t|he front|
|00003380| 20 6f 72 20 62 61 63 6b | 20 6f 66 20 61 20 73 74 | or back| of a st|
|00003390| 72 75 63 74 75 72 65 20 | 69 73 20 6c 65 73 73 20 |ructure |is less |
|000033a0| 65 66 66 69 63 69 65 6e | 74 20 74 68 61 6e 20 66 |efficien|t than f|
|000033b0| 6f 72 20 74 68 65 20 75 | 6e 62 6f 75 6e 64 65 64 |or the u|nbounded|
|000033c0| 20 66 6f 72 6d 2e 0d 55 | 6e 62 6f 75 6e 64 65 64 | form..U|nbounded|
|000033d0| 20 63 6f 6e 74 61 69 6e | 65 72 73 0d 54 68 65 20 | contain|ers.The |
|000033e0| 75 6e 62 6f 75 6e 64 65 | 64 20 63 6f 6e 74 61 69 |unbounde|d contai|
|000033f0| 6e 65 72 20 69 73 20 73 | 70 61 63 65 2d 65 66 66 |ner is s|pace-eff|
|00003400| 69 63 69 65 6e 74 2c 20 | 62 75 74 20 72 65 71 75 |icient, |but requ|
|00003410| 69 72 65 73 20 61 6c 6c | 6f 63 61 74 69 6f 6e 20 |ires all|ocation |
|00003420| 66 6f 72 20 65 76 65 72 | 79 20 6e 65 77 20 69 74 |for ever|y new it|
|00003430| 65 6d 20 28 64 65 70 65 | 6e 64 65 6e 74 20 75 70 |em (depe|ndent up|
|00003440| 6f 6e 20 74 68 65 20 73 | 74 6f 72 61 67 65 20 6d |on the s|torage m|
|00003450| 61 6e 61 67 65 6d 65 6e | 74 20 70 6f 6c 69 63 79 |anagemen|t policy|
|00003460| 2c 20 61 73 20 64 69 73 | 63 75 73 73 65 64 20 69 |, as dis|cussed i|
|00003470| 6e 20 61 20 6c 61 74 65 | 72 20 73 65 63 74 69 6f |n a late|r sectio|
|00003480| 6e 29 2e 20 49 6e 64 65 | 78 69 6e 67 20 69 73 20 |n). Inde|xing is |
|00003490| 6c 65 73 73 20 65 66 66 | 69 63 69 65 6e 74 20 74 |less eff|icient t|
|000034a0| 68 61 6e 20 74 68 65 20 | 64 79 6e 61 6d 69 63 20 |han the |dynamic |
|000034b0| 66 6f 72 6d 2c 20 61 6c | 74 68 6f 75 67 68 20 61 |form, al|though a|
|000034c0| 63 63 65 73 73 20 74 6f | 20 74 68 65 20 6d 6f 73 |ccess to| the mos|
|000034d0| 74 20 72 65 63 65 6e 74 | 6c 79 20 61 63 63 65 73 |t recent|ly acces|
|000034e0| 73 65 64 20 69 74 65 6d | 20 69 73 20 63 61 63 68 |sed item| is cach|
|000034f0| 65 64 2e 20 0d 54 68 65 | 20 75 6e 62 6f 75 6e 64 |ed. .The| unbound|
|00003500| 65 64 20 66 6f 72 6d 20 | 69 73 20 62 65 73 74 20 |ed form |is best |
|00003510| 73 75 69 74 65 64 20 74 | 6f 20 73 74 72 75 63 74 |suited t|o struct|
|00003520| 75 72 65 73 20 77 68 6f | 73 65 20 73 69 7a 65 20 |ures who|se size |
|00003530| 76 61 72 69 65 73 20 77 | 69 64 65 6c 79 20 64 75 |varies w|idely du|
|00003540| 72 69 6e 67 20 69 74 73 | 20 6c 69 66 65 74 69 6d |ring its| lifetim|
|00003550| 65 2c 20 6f 72 20 74 68 | 61 74 20 72 65 71 75 69 |e, or th|at requi|
|00003560| 72 65 73 20 65 78 74 65 | 6e 73 69 76 65 20 69 6e |res exte|nsive in|
|00003570| 73 65 72 74 69 6f 6e 2f | 64 65 6c 65 74 69 6f 6e |sertion/|deletion|
|00003580| 20 6f 74 68 65 72 20 74 | 68 61 6e 20 61 74 20 74 | other t|han at t|
|00003590| 68 65 20 66 72 6f 6e 74 | 20 6f 72 20 62 61 63 6b |he front| or back|
|000035a0| 20 6f 66 20 74 68 65 20 | 73 74 72 75 63 74 75 72 | of the |structur|
|000035b0| 65 2e 20 54 68 75 73 2c | 20 74 68 65 20 66 6f 72 |e. Thus,| the for|
|000035c0| 6d 20 69 73 20 61 70 70 | 6c 69 63 61 62 6c 65 20 |m is app|licable |
|000035d0| 69 6e 20 74 68 6f 73 65 | 20 63 61 73 65 73 20 77 |in those| cases w|
|000035e0| 68 65 72 65 20 74 68 65 | 20 75 6c 74 69 6d 61 74 |here the| ultimat|
|000035f0| 65 20 73 69 7a 65 20 6f | 66 20 74 68 65 20 73 74 |e size o|f the st|
|00003600| 72 75 63 74 75 72 65 20 | 63 61 6e 6e 6f 74 20 62 |ructure |cannot b|
|00003610| 65 20 70 72 65 64 69 63 | 74 65 64 2c 20 61 6e 64 |e predic|ted, and|
|00003620| 20 77 68 65 72 65 20 61 | 6c 6c 6f 63 61 74 69 6e | where a|llocatin|
|00003630| 67 20 61 6e 64 20 64 65 | 61 6c 6c 6f 63 61 74 69 |g and de|allocati|
|00003640| 6e 67 20 73 74 6f 72 61 | 67 65 20 66 72 6f 6d 20 |ng stora|ge from |
|00003650| 74 68 65 20 68 65 61 70 | 20 69 73 20 6e 65 69 74 |the heap| is neit|
|00003660| 68 65 72 20 74 6f 6f 20 | 63 6f 73 74 6c 79 20 6e |her too |costly n|
|00003670| 6f 72 20 75 6e 73 61 66 | 65 20 28 61 73 20 69 74 |or unsaf|e (as it|
|00003680| 20 6d 61 79 20 62 65 20 | 69 6e 20 63 65 72 74 61 | may be |in certa|
|00003690| 69 6e 20 74 69 6d 65 2d | 63 72 69 74 69 63 61 6c |in time-|critical|
|000036a0| 20 61 70 70 6c 69 63 61 | 74 69 6f 6e 73 29 2e 0d | applica|tions)..|
|000036b0| 41 6c 6c 20 6f 66 20 74 | 68 65 20 73 74 72 75 63 |All of t|he struc|
|000036c0| 74 75 72 65 73 20 69 6e | 20 74 68 69 73 20 63 6f |tures in| this co|
|000036d0| 6d 70 6f 6e 65 6e 74 20 | 72 65 71 75 69 72 65 20 |mponent |require |
|000036e0| 74 68 69 73 20 72 61 6e | 67 65 20 6f 66 20 61 6c |this ran|ge of al|
|000036f0| 74 65 72 6e 61 74 69 76 | 65 73 20 28 61 73 20 77 |ternativ|es (as w|
|00003700| 65 6c 6c 20 61 73 20 74 | 68 65 20 64 79 6e 61 6d |ell as t|he dynam|
|00003710| 69 63 2c 20 74 6f 20 62 | 65 20 64 69 73 63 75 73 |ic, to b|e discus|
|00003720| 73 65 64 20 6c 61 74 65 | 72 29 2e 0d 54 68 65 20 |sed late|r)..The |
|00003730| 42 43 5f 54 55 6e 62 6f | 75 6e 64 65 64 20 63 6c |BC_TUnbo|unded cl|
|00003740| 61 73 73 20 70 72 6f 76 | 69 64 65 73 20 61 20 76 |ass prov|ides a v|
|00003750| 65 72 79 20 65 66 66 69 | 63 69 65 6e 74 20 6c 69 |ery effi|cient li|
|00003760| 6e 6b 65 64 2d 6c 69 73 | 74 20 73 74 72 75 63 74 |nked-lis|t struct|
|00003770| 75 72 65 20 74 68 61 74 | 20 75 73 65 73 20 69 74 |ure that| uses it|
|00003780| 65 6d 73 20 61 6c 6c 6f | 63 61 74 65 64 20 66 72 |ems allo|cated fr|
|00003790| 6f 6d 20 74 68 65 20 68 | 65 61 70 2e 20 54 68 69 |om the h|eap. Thi|
|000037a0| 73 20 72 65 70 72 65 73 | 65 6e 74 61 74 69 6f 6e |s repres|entation|
|000037b0| 20 73 61 76 65 73 20 74 | 69 6d 65 20 62 75 74 20 | saves t|ime but |
|000037c0| 75 73 65 73 20 6d 6f 72 | 65 20 73 70 61 63 65 2c |uses mor|e space,|
|000037d0| 20 62 65 63 61 75 73 65 | 20 66 6f 72 20 65 61 63 | because| for eac|
|000037e0| 68 20 69 74 65 6d 2c 20 | 73 74 6f 72 61 67 65 20 |h item, |storage |
|000037f0| 6d 75 73 74 20 62 65 20 | 73 61 76 65 64 20 66 6f |must be |saved fo|
|00003800| 72 20 61 20 70 6f 69 6e | 74 65 72 20 74 6f 20 74 |r a poin|ter to t|
|00003810| 68 65 20 6e 65 78 74 20 | 69 74 65 6d 2e 20 0d 54 |he next |item. .T|
|00003820| 68 65 20 43 6f 6c 6c 65 | 63 74 69 6f 6e 73 20 63 |he Colle|ctions c|
|00003830| 6f 6d 70 6f 6e 65 6e 74 | 20 75 73 65 73 20 61 67 |omponent| uses ag|
|00003840| 67 72 65 67 61 74 69 6f | 6e 20 74 6f 20 70 6c 61 |gregatio|n to pla|
|00003850| 63 65 20 74 68 65 73 65 | 20 6c 6f 77 65 72 2d 6c |ce these| lower-l|
|00003860| 65 76 65 6c 20 63 6c 61 | 73 73 65 73 20 69 6e 20 |evel cla|sses in |
|00003870| 74 68 65 20 66 61 6d 69 | 6c 79 20 6f 66 20 63 6c |the fami|ly of cl|
|00003880| 61 73 73 65 73 2e 20 53 | 70 65 63 69 66 69 63 61 |asses. S|pecifica|
|00003890| 6c 6c 79 2c 20 70 68 79 | 73 69 63 61 6c 20 63 6f |lly, phy|sical co|
|000038a0| 6e 74 61 69 6e 6d 65 6e | 74 20 69 73 20 75 73 65 |ntainmen|t is use|
|000038b0| 64 20 62 79 20 76 61 6c | 75 65 20 77 69 74 68 20 |d by val|ue with |
|000038c0| 70 72 6f 74 65 63 74 65 | 64 20 61 63 63 65 73 73 |protecte|d access|
|000038d0| 2c 20 6d 65 61 6e 69 6e | 67 20 74 68 61 74 20 74 |, meanin|g that t|
|000038e0| 68 69 73 20 6c 6f 77 65 | 72 2d 6c 65 76 65 6c 20 |his lowe|r-level |
|000038f0| 72 65 70 72 65 73 65 6e | 74 61 74 69 6f 6e 20 69 |represen|tation i|
|00003900| 73 20 61 63 63 65 73 73 | 69 62 6c 65 20 6f 6e 6c |s access|ible onl|
|00003910| 79 20 74 6f 20 73 75 62 | 63 6c 61 73 73 65 73 20 |y to sub|classes |
|00003920| 61 6e 64 20 66 72 69 65 | 6e 64 73 2e 20 0d 4e 6f |and frie|nds. .No|
|00003930| 74 65 0d 41 20 6d 69 78 | 69 6e 20 73 74 79 6c 65 |te.A mix|in style|
|00003940| 20 77 61 73 20 61 6c 73 | 6f 20 63 6f 6e 73 69 64 | was als|o consid|
|00003950| 65 72 65 64 2c 20 77 68 | 65 72 65 20 74 68 65 20 |ered, wh|ere the |
|00003960| 42 43 5f 54 55 6e 62 6f | 75 6e 64 65 64 20 63 6c |BC_TUnbo|unded cl|
|00003970| 61 73 73 20 77 61 73 20 | 69 6e 74 72 6f 64 75 63 |ass was |introduc|
|00003980| 65 64 20 61 73 20 61 20 | 70 72 6f 74 65 63 74 65 |ed as a |protecte|
|00003990| 64 20 73 75 70 65 72 63 | 6c 61 73 73 65 73 2e 20 |d superc|lasses. |
|000039a0| 54 68 69 73 20 64 65 73 | 69 67 6e 20 77 61 73 20 |This des|ign was |
|000039b0| 72 65 6a 65 63 74 65 64 | 20 62 65 63 61 75 73 65 |rejected| because|
|000039c0| 20 69 74 20 70 72 6f 76 | 65 64 20 74 6f 20 62 65 | it prov|ed to be|
|000039d0| 20 63 6f 6e 63 65 70 74 | 75 61 6c 6c 79 20 64 69 | concept|ually di|
|000039e0| 66 66 69 63 75 6c 74 20 | 66 6f 72 20 63 6c 69 65 |fficult |for clie|
|000039f0| 6e 74 73 2c 20 61 6e 64 | 20 61 6c 73 6f 20 76 69 |nts, and| also vi|
|00003a00| 6f 6c 61 74 65 64 20 61 | 20 70 72 69 6d 61 72 79 |olated a| primary|
|00003a10| 20 74 65 73 74 20 66 6f | 72 20 69 6e 68 65 72 69 | test fo|r inheri|
|00003a20| 74 61 6e 63 65 3a 20 61 | 20 42 43 5f 54 55 6e 62 |tance: a| BC_TUnb|
|00003a30| 6f 75 6e 64 65 64 51 75 | 65 75 65 20 63 6c 61 73 |oundedQu|eue clas|
|00003a40| 73 20 69 73 20 6e 6f 74 | 20 61 20 6b 69 6e 64 20 |s is not| a kind |
|00003a50| 6f 66 20 42 43 5f 54 55 | 6e 62 6f 75 6e 64 65 64 |of BC_TU|nbounded|
|00003a60| 2e 0d 0d 54 68 65 20 75 | 6e 62 6f 75 6e 64 65 64 |...The u|nbounded|
|00003a70| 20 66 6f 72 6d 20 72 65 | 71 75 69 72 65 73 20 61 | form re|quires a|
|00003a80| 20 73 74 6f 72 61 67 65 | 20 6d 61 6e 61 67 65 72 | storage| manager|
|00003a90| 20 63 6c 61 73 73 2c 20 | 77 68 6f 73 65 20 72 65 | class, |whose re|
|00003aa0| 73 70 6f 6e 73 69 62 69 | 6c 69 74 79 20 69 73 20 |sponsibi|lity is |
|00003ab0| 74 6f 20 70 72 6f 76 69 | 64 65 20 61 20 70 61 72 |to provi|de a par|
|00003ac0| 74 69 63 75 6c 61 72 20 | 73 74 6f 72 61 67 65 20 |ticular |storage |
|00003ad0| 6d 61 6e 61 67 65 6d 65 | 6e 74 20 70 6f 6c 69 63 |manageme|nt polic|
|00003ae0| 79 20 28 73 65 65 20 d2 | 4d 61 6e 61 67 69 6e 67 |y (see .|Managing|
|00003af0| 20 73 74 6f 72 61 67 65 | d3 20 6f 6e 20 70 61 67 | storage|. on pag|
|00003b00| 65 20 31 32 29 2e 0d 54 | 68 65 20 75 6e 62 6f 75 |e 12)..T|he unbou|
|00003b10| 6e 64 65 64 20 66 6f 72 | 6d 20 64 6f 65 73 20 6e |nded for|m does n|
|00003b20| 6f 74 20 75 73 65 20 76 | 69 72 74 75 61 6c 20 6d |ot use v|irtual m|
|00003b30| 65 74 68 6f 64 73 2e 20 | 54 68 75 73 2c 20 42 43 |ethods. |Thus, BC|
|00003b40| 5f 54 55 6e 62 6f 75 6e | 64 65 64 20 63 61 6e 6e |_TUnboun|ded cann|
|00003b50| 6f 74 20 68 61 76 65 20 | 73 75 62 63 6c 61 73 73 |ot have |subclass|
|00003b60| 65 73 2e 20 54 68 69 73 | 20 74 72 61 64 65 73 20 |es. This| trades |
|00003b70| 6f 66 66 20 66 6c 65 78 | 69 62 69 6c 69 74 79 20 |off flex|ibility |
|00003b80| 66 6f 72 20 73 70 65 65 | 64 20 61 6e 64 20 72 65 |for spee|d and re|
|00003b90| 61 73 6f 6e 61 62 6c 65 | 20 6d 65 6d 6f 72 79 20 |asonable| memory |
|00003ba0| 75 73 65 2e 20 41 73 20 | 70 61 72 74 20 6f 66 20 |use. As |part of |
|00003bb0| 74 68 69 73 20 74 72 61 | 64 65 2d 6f 66 66 2c 20 |this tra|de-off, |
|00003bc0| 63 65 72 74 61 69 6e 20 | 6d 65 74 68 6f 64 73 20 |certain |methods |
|00003bd0| 61 72 65 20 70 6c 61 63 | 65 64 20 69 6e 6c 69 6e |are plac|ed inlin|
|00003be0| 65 20 66 6f 72 20 73 70 | 65 65 64 3b 20 66 6f 72 |e for sp|eed; for|
|00003bf0| 20 65 78 61 6d 70 6c 65 | 2c 20 6d 65 74 68 6f 64 | example|, method|
|00003c00| 73 20 74 68 61 74 20 69 | 6e 71 75 69 72 65 20 61 |s that i|nquire a|
|00003c10| 62 6f 75 74 20 74 68 65 | 20 73 74 61 74 65 20 6f |bout the| state o|
|00003c20| 66 20 61 6e 20 6f 62 6a | 65 63 74 20 61 6e 64 20 |f an obj|ect and |
|00003c30| 74 68 65 6e 20 72 65 74 | 75 72 6e 20 61 20 73 69 |then ret|urn a si|
|00003c40| 6d 70 6c 65 20 76 61 6c | 75 65 20 61 72 65 20 75 |mple val|ue are u|
|00003c50| 73 75 61 6c 6c 79 20 67 | 6f 6f 64 20 63 61 6e 64 |sually g|ood cand|
|00003c60| 69 64 61 74 65 73 20 66 | 6f 72 20 69 6e 6c 69 6e |idates f|or inlin|
|00003c70| 69 6e 67 2e 0d 54 68 65 | 20 64 65 73 69 67 6e 20 |ing..The| design |
|00003c80| 6f 66 20 74 68 65 20 75 | 6e 62 6f 75 6e 64 65 64 |of the u|nbounded|
|00003c90| 20 73 75 70 70 6f 72 74 | 20 63 6c 61 73 73 20 72 | support| class r|
|00003ca0| 61 69 73 65 73 20 73 6f | 6d 65 20 69 73 73 75 65 |aises so|me issue|
|00003cb0| 73 20 63 6f 6e 63 65 72 | 6e 69 6e 67 20 74 68 65 |s concer|ning the|
|00003cc0| 20 75 73 65 20 6f 66 20 | 72 65 66 65 72 65 6e 63 | use of |referenc|
|00003cd0| 65 73 2e 20 49 6e 20 43 | 2b 2b 2c 20 72 65 66 65 |es. In C|++, refe|
|00003ce0| 72 65 6e 63 65 73 20 70 | 72 6f 76 69 64 65 20 61 |rences p|rovide a|
|00003cf0| 6e 20 61 6c 69 61 73 69 | 6e 67 20 6d 65 63 68 61 |n aliasi|ng mecha|
|00003d00| 6e 69 73 6d 20 74 68 61 | 74 20 63 61 6e 20 69 6d |nism tha|t can im|
|00003d10| 70 72 6f 76 65 20 70 65 | 72 66 6f 72 6d 61 6e 63 |prove pe|rformanc|
|00003d20| 65 2e 20 48 6f 77 65 76 | 65 72 2c 20 72 65 66 65 |e. Howev|er, refe|
|00003d30| 72 65 6e 63 65 73 20 6d | 75 73 74 20 62 65 20 75 |rences m|ust be u|
|00003d40| 73 65 64 20 63 61 72 65 | 66 75 6c 6c 79 20 74 6f |sed care|fully to|
|00003d50| 20 61 76 6f 69 64 20 63 | 72 65 61 74 69 6e 67 20 | avoid c|reating |
|00003d60| 75 6e 73 61 66 65 20 73 | 69 74 75 61 74 69 6f 6e |unsafe s|ituation|
|00003d70| 73 20 61 74 20 72 75 6e | 74 69 6d 65 2e 20 54 68 |s at run|time. Th|
|00003d80| 69 73 20 63 6f 6d 70 6f | 6e 65 6e 74 20 75 73 65 |is compo|nent use|
|00003d90| 73 20 72 65 66 65 72 65 | 6e 63 65 73 20 74 6f 20 |s refere|nces to |
|00003da0| 69 6d 70 72 6f 76 65 20 | 74 68 65 20 70 65 72 66 |improve |the perf|
|00003db0| 6f 72 6d 61 6e 63 65 20 | 6f 66 20 70 61 73 73 69 |ormance |of passi|
|00003dc0| 6e 67 20 61 72 67 75 6d | 65 6e 74 73 20 74 6f 20 |ng argum|ents to |
|00003dd0| 6d 65 74 68 6f 64 73 2e | 20 54 68 65 20 43 6f 6c |methods.| The Col|
|00003de0| 6c 65 63 74 69 6f 6e 73 | 20 63 6c 61 73 73 65 73 |lections| classes|
|00003df0| 20 67 65 6e 65 72 61 6c | 6c 79 20 64 6f 20 6e 6f | general|ly do no|
|00003e00| 74 20 70 61 73 73 20 70 | 72 69 6d 69 74 69 76 65 |t pass p|rimitive|
|00003e10| 20 6f 62 6a 65 63 74 73 | 20 28 73 75 63 68 20 61 | objects| (such a|
|00003e20| 73 20 69 6e 74 65 67 65 | 72 73 29 2c 20 62 65 63 |s intege|rs), bec|
|00003e30| 61 75 73 65 20 69 74 20 | 69 73 20 6c 69 6b 65 6c |ause it |is likel|
|00003e40| 79 20 74 6f 20 6d 61 6b | 65 20 74 68 65 20 63 6f |y to mak|e the co|
|00003e50| 64 65 20 73 6c 6f 77 65 | 72 2e 20 41 64 64 69 74 |de slowe|r. Addit|
|00003e60| 69 6f 6e 61 6c 6c 79 2c | 20 43 2b 2b 20 73 65 6d |ionally,| C++ sem|
|00003e70| 61 6e 74 69 63 73 20 69 | 6e 74 72 6f 64 75 63 65 |antics i|ntroduce|
|00003e80| 20 73 6f 6d 65 20 70 6f | 74 65 6e 74 69 61 6c 6c | some po|tentiall|
|00003e90| 79 20 64 61 6e 67 65 72 | 6f 75 73 20 70 72 6f 62 |y danger|ous prob|
|00003ea0| 6c 65 6d 73 20 77 68 65 | 6e 20 74 65 6d 70 6f 72 |lems whe|n tempor|
|00003eb0| 61 72 79 20 6f 62 6a 65 | 63 74 73 20 61 72 65 20 |ary obje|cts are |
|00003ec0| 75 73 65 64 2e 0d 48 6f | 77 65 76 65 72 2c 20 61 |used..Ho|wever, a|
|00003ed0| 6c 6c 20 73 74 72 75 63 | 74 75 72 65 73 20 73 74 |ll struc|tures st|
|00003ee0| 6f 72 65 20 76 61 6c 75 | 65 73 2c 20 6e 6f 74 20 |ore valu|es, not |
|00003ef0| 72 65 66 65 72 65 6e 63 | 65 73 2c 20 69 6e 20 74 |referenc|es, in t|
|00003f00| 68 65 69 72 20 72 65 73 | 70 65 63 74 69 76 65 20 |heir res|pective |
|00003f10| 63 6f 6e 63 72 65 74 65 | 20 66 6f 72 6d 73 2e 20 |concrete| forms. |
|00003f20| 54 68 69 73 20 73 74 79 | 6c 65 20 70 72 65 76 65 |This sty|le preve|
|00003f30| 6e 74 73 20 63 72 65 61 | 74 69 6e 67 20 72 65 66 |nts crea|ting ref|
|00003f40| 65 72 65 6e 63 65 73 20 | 74 6f 20 74 72 61 6e 73 |erences |to trans|
|00003f50| 69 65 6e 74 20 6f 62 6a | 65 63 74 73 20 6f 6e 20 |ient obj|ects on |
|00003f60| 74 68 65 20 72 75 6e 74 | 69 6d 65 20 73 74 61 63 |the runt|ime stac|
|00003f70| 6b 2e 0d 4e 6f 74 65 0d | 46 6f 72 20 74 68 65 20 |k..Note.|For the |
|00003f80| 73 61 6d 65 20 72 65 61 | 73 6f 6e 2c 20 61 6e 20 |same rea|son, an |
|00003f90| 61 6c 74 65 72 6e 61 74 | 69 76 65 20 64 65 73 69 |alternat|ive desi|
|00003fa0| 67 6e 20 74 68 61 74 20 | 73 74 6f 72 65 64 20 70 |gn that |stored p|
|00003fb0| 6f 69 6e 74 65 72 73 20 | 74 6f 20 69 74 65 6d 73 |ointers |to items|
|00003fc0| 20 77 61 73 20 72 65 6a | 65 63 74 65 64 2c 20 62 | was rej|ected, b|
|00003fd0| 65 63 61 75 73 65 20 74 | 68 61 74 20 61 70 70 72 |ecause t|hat appr|
|00003fe0| 6f 61 63 68 20 65 78 68 | 69 62 69 74 73 20 75 6e |oach exh|ibits un|
|00003ff0| 64 65 73 69 72 61 62 6c | 65 20 62 65 68 61 76 69 |desirabl|e behavi|
|00004000| 6f 72 20 77 68 65 6e 20 | 69 6e 73 74 61 6e 74 69 |or when |instanti|
|00004010| 61 74 69 6e 67 20 61 20 | 74 65 6d 70 6c 61 74 65 |ating a |template|
|00004020| 20 77 69 74 68 20 62 75 | 69 6c 74 2d 69 6e 20 74 | with bu|ilt-in t|
|00004030| 79 70 65 73 2e 20 0d 0d | 54 68 65 73 65 20 69 73 |ypes. ..|These is|
|00004040| 73 75 65 73 20 61 72 65 | 20 73 69 67 6e 69 66 69 |sues are| signifi|
|00004050| 63 61 6e 74 20 77 68 65 | 6e 20 64 65 73 69 67 6e |cant whe|n design|
|00004060| 69 6e 67 20 74 68 65 20 | 69 6e 74 65 72 66 61 63 |ing the |interfac|
|00004070| 65 20 74 6f 20 61 20 66 | 72 61 6d 65 77 6f 72 6b |e to a f|ramework|
|00004080| 20 69 6e 76 6f 6c 76 69 | 6e 67 20 74 65 6d 70 6c | involvi|ng templ|
|00004090| 61 74 65 20 63 6c 61 73 | 73 65 73 2c 20 73 69 6e |ate clas|ses, sin|
|000040a0| 63 65 20 63 6c 69 65 6e | 74 73 20 63 61 6e 20 69 |ce clien|ts can i|
|000040b0| 6e 73 74 61 6e 74 69 61 | 74 65 20 74 68 65 20 74 |nstantia|te the t|
|000040c0| 65 6d 70 6c 61 74 65 73 | 20 77 69 74 68 20 61 72 |emplates| with ar|
|000040d0| 62 69 74 72 61 72 79 20 | 74 79 70 65 73 2e 20 54 |bitrary |types. T|
|000040e0| 68 65 72 65 20 61 72 65 | 20 74 68 72 65 65 20 63 |here are| three c|
|000040f0| 61 73 65 73 20 74 6f 20 | 63 6f 6e 73 69 64 65 72 |ases to |consider|
|00004100| 2e 0d 09 31 2e 09 42 75 | 69 6c 74 2d 69 6e 20 74 |...1..Bu|ilt-in t|
|00004110| 79 70 65 73 20 63 61 6e | 20 62 65 20 70 61 73 73 |ypes can| be pass|
|00004120| 65 64 20 62 79 20 72 65 | 66 65 72 65 6e 63 65 20 |ed by re|ference |
|00004130| 61 6e 64 20 63 6f 70 69 | 65 64 20 69 6e 74 6f 20 |and copi|ed into |
|00004140| 63 6f 6e 63 72 65 74 65 | 20 72 65 70 72 65 73 65 |concrete| represe|
|00004150| 6e 74 61 74 69 6f 6e 73 | 20 77 69 74 68 20 6e 6f |ntations| with no|
|00004160| 20 64 69 66 66 69 63 75 | 6c 74 79 2e 20 44 65 63 | difficu|lty. Dec|
|00004170| 6c 61 72 69 6e 67 20 74 | 68 65 20 61 72 67 75 6d |laring t|he argum|
|00004180| 65 6e 74 20 74 79 70 65 | 73 20 61 73 20 63 6f 6e |ent type|s as con|
|00004190| 73 74 61 6e 74 20 72 65 | 66 65 72 65 6e 63 65 73 |stant re|ferences|
|000041a0| 20 61 76 6f 69 64 73 20 | 77 61 72 6e 69 6e 67 73 | avoids |warnings|
|000041b0| 20 64 75 65 20 74 6f 20 | 74 65 6d 70 6f 72 61 72 | due to |temporar|
|000041c0| 69 65 73 20 69 6e 76 6f | 6c 76 65 64 20 69 6e 20 |ies invo|lved in |
|000041d0| 74 79 70 65 20 63 6f 6e | 76 65 72 73 69 6f 6e 2e |type con|version.|
|000041e0| 0d 09 32 2e 09 55 73 65 | 72 2d 64 65 66 69 6e 65 |..2..Use|r-define|
|000041f0| 64 20 74 79 70 65 73 20 | 63 61 6e 20 62 65 20 70 |d types |can be p|
|00004200| 61 73 73 65 64 20 62 79 | 20 72 65 66 65 72 65 6e |assed by| referen|
|00004210| 63 65 20 61 6e 64 20 63 | 6f 70 69 65 64 2c 20 62 |ce and c|opied, b|
|00004220| 75 74 20 6f 6e 6c 79 20 | 69 66 20 74 68 65 79 20 |ut only |if they |
|00004230| 70 72 6f 76 69 64 65 20 | 63 6f 70 79 20 63 6f 6e |provide |copy con|
|00004240| 73 74 72 75 63 74 6f 72 | 73 20 61 6e 64 20 74 68 |structor|s and th|
|00004250| 65 20 61 73 73 69 67 6e | 6d 65 6e 74 20 6f 70 65 |e assign|ment ope|
|00004260| 72 61 74 6f 72 2e 20 41 | 6c 74 68 6f 75 67 68 20 |rator. A|lthough |
|00004270| 74 68 65 20 72 65 66 65 | 72 65 6e 63 65 73 20 70 |the refe|rences p|
|00004280| 65 72 6d 69 74 20 70 6f | 6c 79 6d 6f 72 70 68 69 |ermit po|lymorphi|
|00004290| 63 20 6f 70 65 72 61 74 | 69 6f 6e 73 20 28 70 61 |c operat|ions (pa|
|000042a0| 73 73 69 6e 67 20 61 6e | 20 6f 62 6a 65 63 74 20 |ssing an| object |
|000042b0| 6f 66 20 61 20 64 65 72 | 69 76 65 64 20 63 6c 61 |of a der|ived cla|
|000042c0| 73 73 20 69 6e 73 74 65 | 61 64 20 6f 66 20 74 68 |ss inste|ad of th|
|000042d0| 65 20 64 65 63 6c 61 72 | 65 64 20 63 6c 61 73 73 |e declar|ed class|
|000042e0| 20 73 75 70 70 6c 69 65 | 64 20 69 6e 20 74 68 65 | supplie|d in the|
|000042f0| 20 69 6e 73 74 61 6e 74 | 69 61 74 69 6f 6e 29 2c | instant|iation),|
|00004300| 20 74 68 65 20 63 6f 70 | 79 69 6e 67 20 77 69 6c | the cop|ying wil|
|00004310| 6c 20 6e 6f 74 20 62 65 | 20 70 6f 6c 79 6d 6f 72 |l not be| polymor|
|00004320| 70 68 69 63 2e 20 41 73 | 73 69 67 6e 69 6e 67 20 |phic. As|signing |
|00004330| 74 68 65 20 6f 62 6a 65 | 63 74 20 6f 66 20 74 68 |the obje|ct of th|
|00004340| 65 20 72 65 70 72 65 73 | 65 6e 74 61 74 69 6f 6e |e repres|entation|
|00004350| 20 77 69 6c 6c 20 d2 73 | 6c 69 63 65 d3 20 74 68 | will .s|lice. th|
|00004360| 65 20 6f 62 6a 65 63 74 | 20 74 6f 20 61 6e 20 69 |e object| to an i|
|00004370| 6e 73 74 61 6e 63 65 20 | 6f 66 20 74 68 65 20 62 |nstance |of the b|
|00004380| 61 73 65 20 63 6c 61 73 | 73 2e 0d 09 33 2e 09 50 |ase clas|s...3..P|
|00004390| 6f 6c 79 6d 6f 72 70 68 | 69 63 20 75 73 65 73 20 |olymorph|ic uses |
|000043a0| 6f 66 20 74 68 65 20 6c | 69 62 72 61 72 79 20 77 |of the l|ibrary w|
|000043b0| 69 6c 6c 20 68 61 76 65 | 20 74 6f 20 69 6e 73 74 |ill have| to inst|
|000043c0| 61 6e 74 69 61 74 65 20 | 74 68 65 20 74 65 6d 70 |antiate |the temp|
|000043d0| 6c 61 74 65 73 20 77 69 | 74 68 20 70 6f 69 6e 74 |lates wi|th point|
|000043e0| 65 72 73 20 74 6f 20 74 | 68 65 20 62 61 73 65 20 |ers to t|he base |
|000043f0| 63 6c 61 73 73 65 73 20 | 69 6e 76 6f 6c 76 65 64 |classes |involved|
|00004400| 2e 20 41 6c 74 68 6f 75 | 67 68 20 70 61 73 73 69 |. Althou|gh passi|
|00004410| 6e 67 20 74 68 65 20 70 | 6f 69 6e 74 65 72 73 20 |ng the p|ointers |
|00004420| 62 79 20 72 65 66 65 72 | 65 6e 63 65 20 64 6f 65 |by refer|ence doe|
|00004430| 73 20 6e 6f 74 20 69 6d | 70 72 6f 76 65 20 70 65 |s not im|prove pe|
|00004440| 72 66 6f 72 6d 61 6e 63 | 65 2c 20 63 6f 70 79 69 |rformanc|e, copyi|
|00004450| 6e 67 20 70 6f 69 6e 74 | 65 72 73 20 69 6e 74 6f |ng point|ers into|
|00004460| 20 74 68 65 20 72 65 70 | 72 65 73 65 6e 74 61 74 | the rep|resentat|
|00004470| 69 6f 6e 20 70 72 65 73 | 65 72 76 65 73 20 74 68 |ion pres|erves th|
|00004480| 65 20 70 6f 6c 79 6d 6f | 72 70 68 69 73 6d 20 6f |e polymo|rphism o|
|00004490| 66 20 74 68 65 20 64 65 | 72 69 76 65 64 20 6f 62 |f the de|rived ob|
|000044a0| 6a 65 63 74 73 2e 0d 42 | 65 63 61 75 73 65 20 76 |jects..B|ecause v|
|000044b0| 61 6c 75 65 73 20 61 72 | 65 20 73 74 6f 72 65 64 |alues ar|e stored|
|000044c0| 20 69 6e 73 74 65 61 64 | 20 6f 66 20 72 65 66 65 | instead| of refe|
|000044d0| 72 65 6e 63 65 73 20 6f | 72 20 70 6f 69 6e 74 65 |rences o|r pointe|
|000044e0| 72 73 20 74 6f 20 69 74 | 65 6d 73 2c 20 73 6f 6d |rs to it|ems, som|
|000044f0| 65 20 72 65 73 70 6f 6e | 73 69 62 69 6c 69 74 69 |e respon|sibiliti|
|00004500| 65 73 20 61 72 65 20 70 | 6c 61 63 65 64 20 6f 6e |es are p|laced on|
|00004510| 20 74 68 65 20 63 6f 6e | 73 74 72 75 63 74 69 6f | the con|structio|
|00004520| 6e 20 61 6e 64 20 64 65 | 73 74 72 75 63 74 69 6f |n and de|structio|
|00004530| 6e 20 6f 66 20 69 74 65 | 6d 73 20 69 6e 20 61 20 |n of ite|ms in a |
|00004540| 63 6f 6c 6c 65 63 74 69 | 6f 6e 73 20 73 74 72 75 |collecti|ons stru|
|00004550| 63 74 75 72 65 2e 20 49 | 6e 20 70 61 72 74 69 63 |cture. I|n partic|
|00004560| 75 6c 61 72 2c 20 74 68 | 65 20 69 74 65 6d 20 63 |ular, th|e item c|
|00004570| 6c 61 73 73 65 73 20 75 | 73 65 64 20 74 6f 20 69 |lasses u|sed to i|
|00004580| 6e 73 74 61 6e 74 69 61 | 74 65 20 61 20 73 74 72 |nstantia|te a str|
|00004590| 75 63 74 75 72 65 20 6d | 75 73 74 20 70 72 6f 76 |ucture m|ust prov|
|000045a0| 69 64 65 20 61 74 20 6c | 65 61 73 74 20 61 20 64 |ide at l|east a d|
|000045b0| 65 66 61 75 6c 74 20 63 | 6f 6e 73 74 72 75 63 74 |efault c|onstruct|
|000045c0| 6f 72 2c 20 61 20 63 6f | 70 79 20 63 6f 6e 73 74 |or, a co|py const|
|000045d0| 72 75 63 74 6f 72 2c 20 | 61 6e 64 20 61 6e 20 61 |ructor, |and an a|
|000045e0| 73 73 69 67 6e 6d 65 6e | 74 20 6f 70 65 72 61 74 |ssignmen|t operat|
|000045f0| 6f 72 2e 0d 41 64 64 69 | 74 69 6f 6e 61 6c 6c 79 |or..Addi|tionally|
|00004600| 2c 20 69 74 65 6d 73 20 | 6d 61 79 20 6e 6f 74 20 |, items |may not |
|00004610| 62 65 20 64 65 73 74 72 | 6f 79 65 64 20 69 6d 6d |be destr|oyed imm|
|00004620| 65 64 69 61 74 65 6c 79 | 20 75 70 6f 6e 20 72 65 |ediately| upon re|
|00004630| 6d 6f 76 61 6c 20 66 72 | 6f 6d 20 61 20 73 74 72 |moval fr|om a str|
|00004640| 75 63 74 75 72 65 2e 0d | 54 68 65 20 6f 70 65 72 |ucture..|The oper|
|00004650| 61 74 6f 72 73 20 66 6f | 72 20 61 73 73 69 67 6e |ators fo|r assign|
|00004660| 6d 65 6e 74 20 61 6e 64 | 20 74 65 73 74 20 66 6f |ment and| test fo|
|00004670| 72 20 65 71 75 61 6c 69 | 74 79 20 61 72 65 20 61 |r equali|ty are a|
|00004680| 6c 73 6f 20 6f 76 65 72 | 6c 6f 61 64 65 64 2e 20 |lso over|loaded. |
|00004690| 41 73 20 6d 65 6e 74 69 | 6f 6e 65 64 20 65 61 72 |As menti|oned ear|
|000046a0| 6c 69 65 72 2c 20 74 68 | 69 73 20 69 64 69 6f 6d |lier, th|is idiom|
|000046b0| 20 70 65 72 6d 69 74 73 | 20 73 75 62 63 6c 61 73 | permits| subclas|
|000046c0| 73 65 73 20 74 6f 20 70 | 72 6f 76 69 64 65 20 6d |ses to p|rovide m|
|000046d0| 6f 72 65 20 65 66 66 69 | 63 69 65 6e 74 20 69 6d |ore effi|cient im|
|000046e0| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 73 20 6f 66 |plementa|tions of|
|000046f0| 20 74 68 65 73 65 20 6f | 70 65 72 61 74 69 6f 6e | these o|peration|
|00004700| 73 20 74 68 61 6e 20 63 | 61 6e 20 74 68 65 20 62 |s than c|an the b|
|00004710| 61 73 65 20 63 6c 61 73 | 73 2c 20 62 65 63 61 75 |ase clas|s, becau|
|00004720| 73 65 20 74 68 65 20 73 | 75 62 63 6c 61 73 73 65 |se the s|ubclasse|
|00004730| 73 20 68 61 76 65 20 64 | 65 74 61 69 6c 65 64 20 |s have d|etailed |
|00004740| 6b 6e 6f 77 6c 65 64 67 | 65 20 6f 66 20 74 68 65 |knowledg|e of the|
|00004750| 69 72 20 6f 77 6e 20 72 | 65 70 72 65 73 65 6e 74 |ir own r|epresent|
|00004760| 61 74 69 6f 6e 2e 20 0d | 54 68 65 20 6f 70 65 72 |ation. .|The oper|
|00004770| 61 74 6f 72 20 6e 65 77 | 20 61 6e 64 20 6f 70 65 |ator new| and ope|
|00004780| 72 61 74 6f 72 20 64 65 | 6c 65 74 65 20 6d 65 74 |rator de|lete met|
|00004790| 68 6f 64 73 20 77 65 72 | 65 20 61 6c 73 6f 20 61 |hods wer|e also a|
|000047a0| 64 64 65 64 2c 20 62 75 | 74 20 77 65 72 65 20 64 |dded, bu|t were d|
|000047b0| 65 63 6c 61 72 65 64 20 | 61 73 20 70 72 6f 74 65 |eclared |as prote|
|000047c0| 63 74 65 64 20 6d 65 6d | 62 65 72 73 2c 20 77 68 |cted mem|bers, wh|
|000047d0| 69 63 68 20 65 66 66 65 | 63 74 69 76 65 6c 79 20 |ich effe|ctively |
|000047e0| 70 72 65 76 65 6e 74 73 | 20 63 6c 69 65 6e 74 73 |prevents| clients|
|000047f0| 20 66 72 6f 6d 20 61 6c | 6c 6f 63 61 74 69 6e 67 | from al|locating|
|00004800| 20 69 6e 73 74 61 6e 63 | 65 73 20 6f 66 20 74 68 | instanc|es of th|
|00004810| 65 20 63 6f 6e 74 61 69 | 6e 65 72 73 2e 0d 54 68 |e contai|ners..Th|
|00004820| 65 20 6d 61 69 6e 20 72 | 65 73 70 6f 6e 73 69 62 |e main r|esponsib|
|00004830| 69 6c 69 74 79 20 6f 66 | 20 74 68 65 20 42 43 5f |ility of| the BC_|
|00004840| 54 55 6e 62 6f 75 6e 64 | 65 64 20 63 6c 61 73 73 |TUnbound|ed class|
|00004850| 20 69 73 20 74 6f 20 6d | 61 6e 61 67 65 20 61 20 | is to m|anage a |
|00004860| 73 69 6e 67 6c 65 20 69 | 74 65 6d 20 74 6f 67 65 |single i|tem toge|
|00004870| 74 68 65 72 20 77 69 74 | 68 20 70 6f 69 6e 74 65 |ther wit|h pointe|
|00004880| 72 73 20 74 6f 20 74 68 | 65 20 6e 65 78 74 20 61 |rs to th|e next a|
|00004890| 6e 64 20 70 72 65 76 69 | 6f 75 73 20 6e 6f 64 65 |nd previ|ous node|
|000048a0| 73 2e 20 42 65 63 61 75 | 73 65 20 74 68 69 73 20 |s. Becau|se this |
|000048b0| 63 6c 61 73 73 20 69 73 | 20 6e 6f 74 20 75 73 65 |class is| not use|
|000048c0| 64 20 62 79 20 63 6c 69 | 65 6e 74 73 20 6f 75 74 |d by cli|ents out|
|000048d0| 73 69 64 65 20 6f 66 20 | 74 68 65 20 63 6f 6d 70 |side of |the comp|
|000048e0| 6f 6e 65 6e 74 2c 20 73 | 74 72 69 63 74 20 72 75 |onent, s|trict ru|
|000048f0| 6c 65 73 20 6f 66 20 65 | 6e 63 61 70 73 75 6c 61 |les of e|ncapsula|
|00004900| 74 69 6f 6e 20 68 61 76 | 65 20 62 65 65 6e 20 72 |tion hav|e been r|
|00004910| 65 6c 61 78 65 64 20 61 | 6e 64 20 61 6c 6c 20 6f |elaxed a|nd all o|
|00004920| 66 20 74 68 65 20 63 6c | 61 73 73 d5 73 20 73 74 |f the cl|ass.s st|
|00004930| 61 74 65 20 68 61 73 20 | 62 65 65 6e 20 65 78 70 |ate has |been exp|
|00004940| 6f 73 65 64 20 61 73 20 | 70 75 62 6c 69 63 20 6d |osed as |public m|
|00004950| 65 6d 62 65 72 73 2c 20 | 74 68 75 73 20 74 72 61 |embers, |thus tra|
|00004960| 64 69 6e 67 20 6f 66 66 | 20 73 61 66 65 74 79 20 |ding off| safety |
|00004970| 66 6f 72 20 65 66 66 69 | 63 69 65 6e 63 79 2e 0d |for effi|ciency..|
|00004980| 54 68 65 20 70 72 6f 74 | 6f 63 6f 6c 20 6f 66 20 |The prot|ocol of |
|00004990| 42 43 5f 54 55 6e 62 6f | 75 6e 64 65 64 20 69 73 |BC_TUnbo|unded is|
|000049a0| 20 69 64 65 6e 74 69 63 | 61 6c 20 74 6f 20 74 68 | identic|al to th|
|000049b0| 61 74 20 6f 66 20 74 68 | 65 20 75 6e 62 6f 75 6e |at of th|e unboun|
|000049c0| 64 65 64 20 66 6f 72 6d | 2c 20 61 6c 74 68 6f 75 |ded form|, althou|
|000049d0| 67 68 20 69 74 73 20 69 | 6d 70 6c 65 6d 65 6e 74 |gh its i|mplement|
|000049e0| 61 74 69 6f 6e 20 69 73 | 20 72 61 64 69 63 61 6c |ation is| radical|
|000049f0| 6c 79 20 64 69 66 66 65 | 72 65 6e 74 2e 0d 57 68 |ly diffe|rent..Wh|
|00004a00| 65 6e 20 79 6f 75 20 69 | 6e 73 74 61 6e 74 69 61 |en you i|nstantia|
|00004a10| 74 65 20 6f 6e 65 20 6f | 66 20 74 68 65 20 63 6c |te one o|f the cl|
|00004a20| 61 73 73 20 74 65 6d 70 | 6c 61 74 65 73 20 74 68 |ass temp|lates th|
|00004a30| 61 74 20 75 73 65 20 61 | 20 64 79 6e 61 6d 69 63 |at use a| dynamic|
|00004a40| 20 63 6f 6e 74 61 69 6e | 65 72 2c 20 79 6f 75 20 | contain|er, you |
|00004a50| 73 75 70 70 6c 79 20 61 | 20 63 68 75 6e 6b 53 69 |supply a| chunkSi|
|00004a60| 7a 65 20 63 6f 6e 73 74 | 72 75 63 74 6f 72 20 61 |ze const|ructor a|
|00004a70| 72 67 75 6d 65 6e 74 2e | 20 54 68 75 73 2c 20 79 |rgument.| Thus, y|
|00004a80| 6f 75 20 63 61 6e 20 74 | 61 69 6c 6f 72 20 65 61 |ou can t|ailor ea|
|00004a90| 63 68 20 69 6e 73 74 61 | 6e 63 65 20 6f 66 20 74 |ch insta|nce of t|
|00004aa0| 68 69 73 20 63 6c 61 73 | 73 20 74 6f 20 61 6e 20 |his clas|s to an |
|00004ab0| 6f 70 74 69 6d 61 6c 20 | 73 69 7a 65 2e 0d 54 68 |optimal |size..Th|
|00004ac0| 65 20 69 6d 70 6c 65 6d | 65 6e 74 61 74 69 6f 6e |e implem|entation|
|00004ad0| 20 6f 66 20 74 68 65 20 | 63 6c 61 73 73 20 42 43 | of the |class BC|
|00004ae0| 5f 54 44 79 6e 61 6d 69 | 63 20 73 68 61 72 65 73 |_TDynami|c shares|
|00004af0| 20 6d 61 6e 79 20 6f 66 | 20 74 68 65 20 73 61 6d | many of| the sam|
|00004b00| 65 20 63 68 61 72 61 63 | 74 65 72 69 73 74 69 63 |e charac|teristic|
|00004b10| 73 20 61 73 20 74 68 61 | 74 20 6f 66 20 74 68 65 |s as tha|t of the|
|00004b20| 20 42 43 5f 54 55 6e 62 | 6f 75 6e 64 65 64 20 63 | BC_TUnb|ounded c|
|00004b30| 6c 61 73 73 2e 20 49 6e | 20 66 61 63 74 2c 20 62 |lass. In| fact, b|
|00004b40| 6f 74 68 20 63 6c 61 73 | 73 65 73 20 68 61 76 65 |oth clas|ses have|
|00004b50| 20 73 75 62 73 74 61 6e | 74 69 61 6c 6c 79 20 74 | substan|tially t|
|00004b60| 68 65 20 73 61 6d 65 20 | 70 75 62 6c 69 63 20 70 |he same |public p|
|00004b70| 72 6f 74 6f 63 6f 6c 2c | 20 74 68 65 20 69 6d 70 |rotocol,| the imp|
|00004b80| 6c 65 6d 65 6e 74 61 74 | 69 6f 6e 20 6f 66 20 65 |lementat|ion of e|
|00004b90| 61 63 68 20 6f 66 20 74 | 68 65 20 63 6f 6e 63 72 |ach of t|he concr|
|00004ba0| 65 74 65 20 63 6c 61 73 | 73 65 73 20 69 6e 20 61 |ete clas|ses in a|
|00004bb0| 20 66 61 6d 69 6c 79 20 | 69 73 20 6c 61 72 67 65 | family |is large|
|00004bc0| 6c 79 20 74 68 65 20 73 | 61 6d 65 20 61 73 20 77 |ly the s|ame as w|
|00004bd0| 65 6c 6c 2e 0d 54 68 65 | 20 69 6d 70 6c 65 6d 65 |ell..The| impleme|
|00004be0| 6e 74 61 74 69 6f 6e 20 | 6f 66 20 74 68 65 20 6d |ntation |of the m|
|00004bf0| 61 70 20 61 6e 64 20 73 | 65 74 20 63 6c 61 73 73 |ap and s|et class|
|00004c00| 65 73 20 61 6c 73 6f 20 | 72 65 76 65 61 6c 73 20 |es also |reveals |
|00004c10| 74 68 61 74 20 74 68 65 | 20 64 79 6e 61 6d 69 63 |that the| dynamic|
|00004c20| 20 61 6e 64 20 75 6e 62 | 6f 75 6e 64 65 64 20 66 | and unb|ounded f|
|00004c30| 6f 72 6d 73 20 6e 65 65 | 64 20 73 6f 6d 65 20 74 |orms nee|d some t|
|00004c40| 75 6e 69 6e 67 20 74 6f | 20 73 61 74 69 73 66 79 |uning to| satisfy|
|00004c50| 20 74 68 65 73 65 20 63 | 6c 61 73 73 65 73 d5 73 | these c|lasses.s|
|00004c60| 20 73 65 6d 61 6e 74 69 | 63 73 2e 20 53 70 65 63 | semanti|cs. Spec|
|00004c70| 69 66 69 63 61 6c 6c 79 | 2c 20 73 65 61 72 63 68 |ifically|, search|
|00004c80| 69 6e 67 20 66 6f 72 20 | 61 6e 20 69 74 65 6d d5 |ing for |an item.|
|00004c90| 73 20 6d 65 6d 62 65 72 | 73 68 69 70 20 69 6e 20 |s member|ship in |
|00004ca0| 61 20 6d 61 70 20 6f 72 | 20 61 20 73 65 74 20 69 |a map or| a set i|
|00004cb0| 73 20 75 6e 61 63 63 65 | 70 74 61 62 6c 79 20 65 |s unacce|ptably e|
|00004cc0| 78 70 65 6e 73 69 76 65 | 20 69 66 20 61 20 6c 6f |xpensive| if a lo|
|00004cd0| 6e 67 20 73 65 71 75 65 | 6e 63 65 20 69 73 20 73 |ng seque|nce is s|
|00004ce0| 65 61 72 63 68 65 64 20 | 73 65 71 75 65 6e 74 69 |earched |sequenti|
|00004cf0| 61 6c 6c 79 2e 20 41 6e | 20 6f 70 65 6e 20 68 61 |ally. An| open ha|
|00004d00| 73 68 20 74 61 62 6c 65 | 20 76 61 73 74 6c 79 20 |sh table| vastly |
|00004d10| 69 6d 70 72 6f 76 65 73 | 20 70 65 72 66 6f 72 6d |improves| perform|
|00004d20| 61 6e 63 65 2e 0d 54 68 | 65 20 61 62 73 74 72 61 |ance..Th|e abstra|
|00004d30| 63 74 69 6f 6e 20 6f 66 | 20 61 6e 20 6f 70 65 6e |ction of| an open|
|00004d40| 20 68 61 73 68 20 74 61 | 62 6c 65 20 69 73 20 73 | hash ta|ble is s|
|00004d50| 74 72 61 69 67 68 74 66 | 6f 72 77 61 72 64 2e 20 |traightf|orward. |
|00004d60| 42 61 73 69 63 61 6c 6c | 79 2c 20 73 75 63 68 20 |Basicall|y, such |
|00004d70| 61 20 74 61 62 6c 65 20 | 63 6f 6e 73 69 73 74 73 |a table |consists|
|00004d80| 20 6f 66 20 61 6e 20 61 | 72 72 61 79 20 6f 66 20 | of an a|rray of |
|00004d90| 73 65 71 75 65 6e 63 65 | 73 3b 20 65 61 63 68 20 |sequence|s; each |
|00004da0| 73 65 71 75 65 6e 63 65 | 20 69 73 20 63 61 6c 6c |sequence| is call|
|00004db0| 65 64 20 61 20 62 75 63 | 6b 65 74 2e 20 57 68 65 |ed a buc|ket. Whe|
|00004dc0| 6e 20 61 6e 20 69 74 65 | 6d 20 69 73 20 70 6c 61 |n an ite|m is pla|
|00004dd0| 63 65 64 20 69 6e 20 74 | 68 65 20 74 61 62 6c 65 |ced in t|he table|
|00004de0| 2c 20 61 20 68 61 73 68 | 20 76 61 6c 75 65 20 69 |, a hash| value i|
|00004df0| 73 20 67 65 6e 65 72 61 | 74 65 64 20 66 72 6f 6d |s genera|ted from|
|00004e00| 20 74 68 65 20 69 74 65 | 6d 20 69 74 73 65 6c 66 | the ite|m itself|
|00004e10| 2c 20 77 68 69 63 68 20 | 69 73 20 74 68 65 6e 20 |, which |is then |
|00004e20| 75 73 65 64 20 74 6f 20 | 73 65 6c 65 63 74 20 61 |used to |select a|
|00004e30| 20 73 70 65 63 69 66 69 | 63 20 62 75 63 6b 65 74 | specifi|c bucket|
|00004e40| 2e 20 54 68 61 74 20 69 | 74 65 6d 20 69 73 20 70 |. That i|tem is p|
|00004e50| 6c 61 63 65 64 20 69 6e | 20 74 68 61 74 20 62 75 |laced in| that bu|
|00004e60| 63 6b 65 74 2c 20 6a 75 | 73 74 20 61 73 20 77 69 |cket, ju|st as wi|
|00004e70| 74 68 20 74 68 65 20 64 | 79 6e 61 6d 69 63 20 61 |th the d|ynamic a|
|00004e80| 6e 64 20 75 6e 62 6f 75 | 6e 64 65 64 20 66 6f 72 |nd unbou|nded for|
|00004e90| 6d 73 2e 20 54 68 75 73 | 2c 20 61 6e 20 6f 70 65 |ms. Thus|, an ope|
|00004ea0| 6e 20 68 61 73 68 20 74 | 61 62 6c 65 20 64 69 76 |n hash t|able div|
|00004eb0| 69 64 65 73 20 61 20 6c | 6f 6e 67 20 73 65 71 75 |ides a l|ong sequ|
|00004ec0| 65 6e 63 65 20 69 6e 74 | 6f 20 73 65 76 65 72 61 |ence int|o severa|
|00004ed0| 6c 20 73 6d 61 6c 6c 65 | 72 20 6f 6e 65 73 2c 20 |l smalle|r ones, |
|00004ee0| 74 68 65 72 65 62 79 20 | 67 72 65 61 74 6c 79 20 |thereby |greatly |
|00004ef0| 61 63 63 65 6c 65 72 61 | 74 69 6e 67 20 73 65 61 |accelera|ting sea|
|00004f00| 72 63 68 65 73 2e 0d 59 | 6f 75 20 61 72 65 20 72 |rches..Y|ou are r|
|00004f10| 65 73 70 6f 6e 73 69 62 | 6c 65 20 66 6f 72 20 70 |esponsib|le for p|
|00004f20| 72 6f 76 69 64 69 6e 67 | 20 74 68 65 20 68 61 73 |roviding| the has|
|00004f30| 68 20 66 75 6e 63 74 69 | 6f 6e 20 77 68 65 6e 20 |h functi|on when |
|00004f40| 79 6f 75 20 75 73 65 20 | 61 6e 20 75 6e 62 6f 75 |you use |an unbou|
|00004f50| 6e 64 65 64 20 66 6f 72 | 6d 2e 0d 4d 61 6e 61 67 |nded for|m..Manag|
|00004f60| 69 6e 67 20 73 74 6f 72 | 61 67 65 0d 53 74 6f 72 |ing stor|age.Stor|
|00004f70| 61 67 65 20 6d 61 6e 61 | 67 65 6d 65 6e 74 20 69 |age mana|gement i|
|00004f80| 73 20 61 6e 20 69 73 73 | 75 65 20 66 6f 72 20 61 |s an iss|ue for a|
|00004f90| 6c 6c 20 64 79 6e 61 6d | 69 63 20 61 6e 64 20 75 |ll dynam|ic and u|
|00004fa0| 6e 62 6f 75 6e 64 65 64 | 20 66 6f 72 6d 73 2c 20 |nbounded| forms, |
|00004fb0| 62 65 63 61 75 73 65 20 | 79 6f 75 20 6d 75 73 74 |because |you must|
|00004fc0| 20 63 6f 6e 73 69 64 65 | 72 20 73 70 65 63 69 66 | conside|r specif|
|00004fd0| 69 63 20 70 6f 6c 69 63 | 69 65 73 20 66 6f 72 20 |ic polic|ies for |
|00004fe0| 61 6c 6c 6f 63 61 74 69 | 6e 67 20 61 6e 64 20 64 |allocati|ng and d|
|00004ff0| 65 61 6c 6c 6f 63 61 74 | 69 6e 67 20 73 65 71 75 |eallocat|ing sequ|
|00005000| 65 6e 63 65 73 20 61 6e | 64 20 6e 6f 64 65 73 20 |ences an|d nodes |
|00005010| 66 72 6f 6d 20 74 68 65 | 20 68 65 61 70 2e 20 0d |from the| heap. .|
|00005020| 55 6e 6d 61 6e 61 67 65 | 64 20 73 74 6f 72 61 67 |Unmanage|d storag|
|00005030| 65 0d 54 68 65 20 70 72 | 6f 74 6f 63 6f 6c 20 66 |e.The pr|otocol f|
|00005040| 6f 72 20 74 68 65 20 42 | 43 5f 43 55 6e 6d 61 6e |or the B|C_CUnman|
|00005050| 61 67 65 64 20 63 6c 61 | 73 73 20 69 73 20 69 6d |aged cla|ss is im|
|00005060| 70 6c 65 6d 65 6e 74 65 | 64 20 62 79 20 69 6e 6c |plemente|d by inl|
|00005070| 69 6e 65 20 63 61 6c 6c | 73 20 74 6f 20 74 68 65 |ine call|s to the|
|00005080| 20 67 6c 6f 62 61 6c 20 | 6f 70 65 72 61 74 6f 72 | global |operator|
|00005090| 73 20 6e 65 77 20 61 6e | 64 20 64 65 6c 65 74 65 |s new an|d delete|
|000050a0| 2e 20 54 68 69 73 20 70 | 6f 6c 69 63 79 20 69 73 |. This p|olicy is|
|000050b0| 20 63 61 6c 6c 65 64 20 | 75 6e 6d 61 6e 61 67 65 | called |unmanage|
|000050c0| 64 2c 20 62 65 63 61 75 | 73 65 20 74 68 65 20 43 |d, becau|se the C|
|000050d0| 6f 6c 6c 65 63 74 69 6f | 6e 73 20 63 6f 6d 70 6f |ollectio|ns compo|
|000050e0| 6e 65 6e 74 20 69 74 73 | 65 6c 66 20 65 66 66 65 |nent its|elf effe|
|000050f0| 63 74 69 76 65 6c 79 20 | 64 6f 65 73 20 6e 6f 74 |ctively |does not|
|00005100| 68 69 6e 67 20 62 65 79 | 6f 6e 64 20 74 68 65 20 |hing bey|ond the |
|00005110| 64 65 66 61 75 6c 74 20 | 70 6f 6c 69 63 79 20 70 |default |policy p|
|00005120| 72 6f 76 69 64 65 64 20 | 62 79 20 74 68 65 20 6c |rovided |by the l|
|00005130| 61 6e 67 75 61 67 65 2e | 20 0d 4e 6f 74 65 0d 54 |anguage.| .Note.T|
|00005140| 68 65 20 6d 65 6d 6f 72 | 79 20 6d 61 6e 61 67 65 |he memor|y manage|
|00005150| 6d 65 6e 74 20 70 72 6f | 76 69 64 65 64 20 62 79 |ment pro|vided by|
|00005160| 20 4f 70 65 6e 44 6f 63 | 20 68 61 73 20 62 65 65 | OpenDoc| has bee|
|00005170| 6e 20 6f 70 74 69 6d 69 | 7a 65 64 20 66 6f 72 20 |n optimi|zed for |
|00005180| 75 73 65 20 77 69 74 68 | 20 6f 62 6a 65 63 74 73 |use with| objects|
|00005190| 2e 20 49 66 20 79 6f 75 | 20 61 72 65 20 75 73 69 |. If you| are usi|
|000051a0| 6e 67 20 74 68 65 20 4d | 65 6d 6f 72 79 20 63 6f |ng the M|emory co|
|000051b0| 6d 70 6f 6e 65 6e 74 2c | 20 79 6f 75 20 63 61 6e |mponent,| you can|
|000051c0| 20 75 73 65 20 75 6e 6d | 61 6e 61 67 65 64 20 6d | use unm|anaged m|
|000051d0| 65 6d 6f 72 79 20 69 6e | 20 6d 6f 73 74 20 63 61 |emory in| most ca|
|000051e0| 73 65 73 2e 0d 0d 46 75 | 72 74 68 65 72 6d 6f 72 |ses...Fu|rthermor|
|000051f0| 65 2c 20 73 74 6f 72 61 | 67 65 20 6d 61 6e 61 67 |e, stora|ge manag|
|00005200| 65 6d 65 6e 74 20 6f 6e | 20 63 65 72 74 61 69 6e |ement on| certain|
|00005210| 20 70 6c 61 74 66 6f 72 | 6d 73 20 63 61 6e 20 62 | platfor|ms can b|
|00005220| 65 20 71 75 69 74 65 20 | 63 6f 6d 70 6c 65 78 2c |e quite |complex,|
|00005230| 20 61 6e 64 20 73 6f 20 | 72 65 71 75 69 72 65 73 | and so |requires|
|00005240| 20 74 68 61 74 20 61 6c | 6c 20 63 6c 61 73 73 65 | that al|l classe|
|00005250| 73 20 75 73 65 20 61 20 | 70 6f 6c 69 63 79 20 74 |s use a |policy t|
|00005260| 61 69 6c 6f 72 65 64 20 | 74 6f 20 74 68 65 20 70 |ailored |to the p|
|00005270| 6c 61 74 66 6f 72 6d 2c | 20 72 61 74 68 65 72 20 |latform,| rather |
|00005280| 74 68 61 6e 20 75 73 69 | 6e 67 20 61 20 67 65 6e |than usi|ng a gen|
|00005290| 65 72 61 6c 20 6f 6e 65 | 20 61 73 73 75 6d 65 64 |eral one| assumed|
|000052a0| 20 62 79 20 74 68 65 20 | 6c 69 62 72 61 72 79 20 | by the |library |
|000052b0| 64 65 73 69 67 6e 65 72 | 20 74 6f 20 77 6f 72 6b |designer| to work|
|000052c0| 20 66 6f 72 20 61 6c 6c | 20 63 69 72 63 75 6d 73 | for all| circums|
|000052d0| 74 61 6e 63 65 73 2e 20 | 42 79 20 63 6c 65 61 72 |tances. |By clear|
|000052e0| 6c 79 20 69 73 6f 6c 61 | 74 69 6e 67 20 74 68 65 |ly isola|ting the|
|000052f0| 73 65 20 70 61 74 74 65 | 72 6e 73 20 6f 66 20 73 |se patte|rns of s|
|00005300| 74 6f 72 61 67 65 20 6d | 61 6e 61 67 65 6d 65 6e |torage m|anagemen|
|00005310| 74 2c 20 74 68 65 20 43 | 6f 6c 6c 65 63 74 69 6f |t, the C|ollectio|
|00005320| 6e 73 20 63 6f 6d 70 6f | 6e 65 6e 74 20 70 72 6f |ns compo|nent pro|
|00005330| 76 69 64 65 73 20 61 20 | 72 6f 62 75 73 74 2c 20 |vides a |robust, |
|00005340| 61 64 61 70 74 61 62 6c | 65 20 6c 69 62 72 61 72 |adaptabl|e librar|
|00005350| 79 2e 0d 43 6f 6e 73 69 | 64 65 72 20 61 20 73 63 |y..Consi|der a sc|
|00005360| 65 6e 61 72 69 6f 20 66 | 6f 72 20 75 73 65 20 77 |enario f|or use w|
|00005370| 69 74 68 20 74 68 65 20 | 75 6e 62 6f 75 6e 64 65 |ith the |unbounde|
|00005380| 64 20 66 6f 72 6d 3a 0d | a5 09 61 43 6c 69 65 6e |d form:.|..aClien|
|00005390| 74 20 63 61 6c 6c 73 20 | 74 68 65 20 41 70 70 65 |t calls |the Appe|
|000053a0| 6e 64 20 6d 65 74 68 6f | 64 20 75 70 6f 6e 20 61 |nd metho|d upon a|
|000053b0| 6e 20 69 6e 73 74 61 6e | 74 69 61 74 69 6f 6e 20 |n instan|tiation |
|000053c0| 6f 66 20 42 43 5f 54 55 | 6e 62 6f 75 6e 64 65 64 |of BC_TU|nbounded|
|000053d0| 51 75 65 75 65 2e 0d a5 | 09 54 68 65 20 42 43 5f |Queue...|.The BC_|
|000053e0| 54 55 6e 62 6f 75 6e 64 | 65 64 51 75 65 75 65 20 |TUnbound|edQueue |
|000053f0| 6f 62 6a 65 63 74 20 69 | 6e 20 74 75 72 6e 20 64 |object i|n turn d|
|00005400| 65 6c 65 67 61 74 65 73 | 20 72 65 73 70 6f 6e 73 |elegates| respons|
|00005410| 69 62 69 6c 69 74 79 20 | 66 6f 72 20 74 68 69 73 |ibility |for this|
|00005420| 20 6f 70 65 72 61 74 69 | 6f 6e 20 74 6f 20 69 74 | operati|on to it|
|00005430| 73 20 6d 65 6d 62 65 72 | 20 6f 62 6a 65 63 74 20 |s member| object |
|00005440| 66 52 65 70 2c 20 61 6e | 20 69 6e 73 74 61 6e 63 |fRep, an| instanc|
|00005450| 65 20 6f 66 20 74 68 65 | 20 63 6c 61 73 73 20 42 |e of the| class B|
|00005460| 43 5f 54 55 6e 62 6f 75 | 6e 64 65 64 2e 0d a5 09 |C_TUnbou|nded....|
|00005470| 42 43 5f 54 55 6e 62 6f | 75 6e 64 65 64 20 61 6c |BC_TUnbo|unded al|
|00005480| 6c 6f 63 61 74 65 73 20 | 61 20 6e 65 77 20 69 6e |locates |a new in|
|00005490| 73 74 61 6e 63 65 20 6f | 66 20 42 43 5f 54 4e 6f |stance o|f BC_TNo|
|000054a0| 64 65 20 62 79 20 69 6e | 76 6f 6b 69 6e 67 20 69 |de by in|voking i|
|000054b0| 74 73 20 6f 70 65 72 61 | 74 6f 72 20 6e 65 77 2e |ts opera|tor new.|
|000054c0| 0d a5 09 54 68 65 20 42 | 43 5f 54 4e 6f 64 65 20 |...The B|C_TNode |
|000054d0| 69 6e 73 74 61 6e 63 65 | 20 69 6e 20 74 75 72 6e |instance| in turn|
|000054e0| 20 64 65 6c 65 67 61 74 | 65 73 20 74 68 65 20 72 | delegat|es the r|
|000054f0| 65 73 70 6f 6e 73 69 62 | 69 6c 69 74 79 20 6f 66 |esponsib|ility of|
|00005500| 20 61 6c 6c 6f 63 61 74 | 69 6f 6e 20 74 6f 20 69 | allocat|ion to i|
|00005510| 74 73 20 73 74 6f 72 61 | 67 65 20 6d 61 6e 61 67 |ts stora|ge manag|
|00005520| 65 72 2c 20 77 68 69 63 | 68 20 69 73 20 6d 61 64 |er, whic|h is mad|
|00005530| 65 20 76 69 73 69 62 6c | 65 20 74 6f 20 74 68 65 |e visibl|e to the|
|00005540| 20 63 6c 61 73 73 20 42 | 43 5f 54 55 6e 62 6f 75 | class B|C_TUnbou|
|00005550| 6e 64 65 64 51 75 65 75 | 65 20 28 61 6e 64 20 69 |ndedQueu|e (and i|
|00005560| 6e 20 74 75 72 6e 20 74 | 6f 20 74 68 65 20 63 6c |n turn t|o the cl|
|00005570| 61 73 73 65 73 20 42 43 | 5f 54 55 6e 62 6f 75 6e |asses BC|_TUnboun|
|00005580| 64 65 64 20 61 6e 64 20 | 42 43 5f 54 4e 6f 64 65 |ded and |BC_TNode|
|00005590| 29 20 61 73 20 61 20 74 | 65 6d 70 6c 61 74 65 20 |) as a t|emplate |
|000055a0| 61 72 67 75 6d 65 6e 74 | 2e 20 54 68 69 73 20 73 |argument|. This s|
|000055b0| 74 6f 72 61 67 65 20 6d | 61 6e 61 67 65 72 20 69 |torage m|anager i|
|000055c0| 73 20 73 68 61 72 65 64 | 20 62 79 20 61 6c 6c 20 |s shared| by all |
|000055d0| 69 6e 73 74 61 6e 63 65 | 73 20 6f 66 20 74 68 65 |instance|s of the|
|000055e0| 20 63 6c 61 73 73 2c 20 | 61 6e 64 20 73 6f 20 73 | class, |and so s|
|000055f0| 65 72 76 65 73 20 74 6f | 20 70 72 6f 76 69 64 65 |erves to| provide|
|00005600| 20 61 20 63 6f 6e 73 69 | 73 74 65 6e 74 20 63 6c | a consi|stent cl|
|00005610| 61 73 73 2d 77 69 64 65 | 20 73 74 6f 72 61 67 65 |ass-wide| storage|
|00005620| 20 6d 61 6e 61 67 65 6d | 65 6e 74 20 70 6f 6c 69 | managem|ent poli|
|00005630| 63 79 2e 0d 42 79 20 74 | 72 65 61 74 69 6e 67 20 |cy..By t|reating |
|00005640| 74 68 65 20 73 74 6f 72 | 61 67 65 20 6d 61 6e 61 |the stor|age mana|
|00005650| 67 65 72 20 61 73 20 61 | 6e 20 61 72 67 75 6d 65 |ger as a|n argume|
|00005660| 6e 74 20 74 6f 20 61 6c | 6c 20 74 68 65 20 75 6e |nt to al|l the un|
|00005670| 62 6f 75 6e 64 65 64 20 | 63 6f 6e 63 72 65 74 65 |bounded |concrete|
|00005680| 20 73 74 72 75 63 74 75 | 72 65 73 2c 20 74 68 65 | structu|res, the|
|00005690| 20 73 74 6f 72 61 67 65 | 20 6d 61 6e 61 67 65 6d | storage| managem|
|000056a0| 65 6e 74 20 70 6f 6c 69 | 63 79 20 69 73 20 64 65 |ent poli|cy is de|
|000056b0| 63 6f 75 70 6c 65 64 20 | 66 72 6f 6d 20 69 74 73 |coupled |from its|
|000056c0| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 2e | impleme|ntation.|
|000056d0| 20 54 68 75 73 2c 20 79 | 6f 75 20 63 61 6e 20 69 | Thus, y|ou can i|
|000056e0| 6e 73 65 72 74 20 79 6f | 75 72 20 6f 77 6e 20 73 |nsert yo|ur own s|
|000056f0| 74 6f 72 61 67 65 20 6d | 61 6e 61 67 65 6d 65 6e |torage m|anagemen|
|00005700| 74 20 70 6f 6c 69 63 79 | 20 77 69 74 68 6f 75 74 |t policy| without|
|00005710| 20 63 68 61 6e 67 69 6e | 67 20 74 68 65 20 6c 69 | changin|g the li|
|00005720| 62 72 61 72 79 2e 20 0d | 54 68 65 20 6f 6e 6c 79 |brary. .|The only|
|00005730| 20 72 65 71 75 69 72 65 | 6d 65 6e 74 20 70 6c 61 | require|ment pla|
|00005740| 63 65 64 20 75 70 6f 6e | 20 74 68 65 20 73 74 6f |ced upon| the sto|
|00005750| 72 61 67 65 20 6d 61 6e | 61 67 65 72 73 20 69 73 |rage man|agers is|
|00005760| 20 74 68 61 74 20 74 68 | 65 79 20 70 72 6f 76 69 | that th|ey provi|
|00005770| 64 65 20 74 68 65 20 73 | 61 6d 65 20 77 65 6c 6c |de the s|ame well|
|00005780| 2d 64 65 66 69 6e 65 64 | 20 70 72 6f 74 6f 63 6f |-defined| protoco|
|00005790| 6c 2e 20 53 70 65 63 69 | 66 69 63 61 6c 6c 79 2c |l. Speci|fically,|
|000057a0| 20 61 6c 6c 20 73 74 6f | 72 61 67 65 20 6d 61 6e | all sto|rage man|
|000057b0| 61 67 65 72 73 20 6d 75 | 73 74 20 65 78 70 6f 72 |agers mu|st expor|
|000057c0| 74 20 41 6c 6c 6f 63 61 | 74 65 20 61 6e 64 20 44 |t Alloca|te and D|
|000057d0| 65 61 6c 6c 6f 63 61 74 | 65 20 6d 65 74 68 6f 64 |eallocat|e method|
|000057e0| 73 2c 20 77 68 69 63 68 | 20 64 69 73 70 65 6e 73 |s, which| dispens|
|000057f0| 65 20 61 6e 64 20 72 65 | 6c 65 61 73 65 20 6d 65 |e and re|lease me|
|00005800| 6d 6f 72 79 2c 20 72 65 | 73 70 65 63 74 69 76 65 |mory, re|spective|
|00005810| 6c 79 2e 0d 4d 61 6e 61 | 67 65 64 20 73 74 6f 72 |ly..Mana|ged stor|
|00005820| 61 67 65 0d 41 6c 74 68 | 6f 75 67 68 20 4f 70 65 |age.Alth|ough Ope|
|00005830| 6e 44 6f 63 20 70 72 6f | 76 69 64 65 73 20 6d 65 |nDoc pro|vides me|
|00005840| 6d 6f 72 79 20 6d 61 6e | 61 67 65 6d 65 6e 74 20 |mory man|agement |
|00005850| 66 6f 72 20 73 6f 2d 63 | 61 6c 6c 65 64 20 75 6e |for so-c|alled un|
|00005860| 6d 61 6e 61 67 65 64 20 | 6d 65 6d 6f 72 79 2c 20 |managed |memory, |
|00005870| 74 68 65 72 65 20 6d 61 | 79 20 62 65 20 73 6f 6d |there ma|y be som|
|00005880| 65 20 63 69 72 63 75 6d | 73 74 61 6e 63 65 73 20 |e circum|stances |
|00005890| 77 68 65 72 65 20 79 6f | 75 20 77 61 6e 74 20 74 |where yo|u want t|
|000058a0| 6f 20 75 73 65 20 6d 61 | 6e 61 67 65 64 20 73 74 |o use ma|naged st|
|000058b0| 6f 72 61 67 65 20 6d 61 | 6e 61 67 65 6d 65 6e 74 |orage ma|nagement|
|000058c0| 2e 20 0d 55 6e 64 65 72 | 20 74 68 69 73 20 70 6f |. .Under| this po|
|000058d0| 6c 69 63 79 2c 20 6e 6f | 64 65 73 20 61 72 65 20 |licy, no|des are |
|000058e0| 61 6c 6c 6f 63 61 74 65 | 64 20 61 6e 64 20 64 65 |allocate|d and de|
|000058f0| 61 6c 6c 6f 63 61 74 65 | 64 20 66 72 6f 6d 20 61 |allocate|d from a|
|00005900| 20 63 6f 6d 6d 6f 6e 20 | 70 6f 6f 6c 20 6f 66 20 | common |pool of |
|00005910| 6d 65 6d 6f 72 79 2e 20 | 55 6e 75 73 65 64 20 6e |memory. |Unused n|
|00005920| 6f 64 65 73 20 6f 66 20 | 61 6e 79 20 6b 69 6e 64 |odes of |any kind|
|00005930| 20 61 72 65 20 72 65 74 | 75 72 6e 65 64 20 74 6f | are ret|urned to|
|00005940| 20 61 20 66 72 65 65 20 | 6c 69 73 74 2c 20 61 6e | a free |list, an|
|00005950| 64 20 61 6c 6c 6f 63 61 | 74 69 6f 6e 20 74 61 6b |d alloca|tion tak|
|00005960| 65 73 20 6e 6f 64 65 73 | 20 66 72 6f 6d 20 74 68 |es nodes| from th|
|00005970| 69 73 20 66 72 65 65 20 | 6c 69 73 74 20 75 6e 6c |is free |list unl|
|00005980| 65 73 73 20 69 74 20 69 | 73 20 65 6d 70 74 79 2c |ess it i|s empty,|
|00005990| 20 69 6e 20 77 68 69 63 | 68 20 63 61 73 65 20 61 | in whic|h case a|
|000059a0| 6e 6f 74 68 65 72 20 63 | 68 75 6e 6b 20 6f 66 20 |nother c|hunk of |
|000059b0| 66 72 65 65 20 6d 65 6d | 6f 72 79 20 69 73 20 61 |free mem|ory is a|
|000059c0| 6c 6c 6f 63 61 74 65 64 | 20 66 72 6f 6d 20 74 68 |llocated| from th|
|000059d0| 65 20 68 65 61 70 2e 20 | 49 6e 20 74 68 69 73 20 |e heap. |In this |
|000059e0| 6d 61 6e 6e 65 72 2c 20 | 74 68 65 20 6e 75 6d 62 |manner, |the numb|
|000059f0| 65 72 20 6f 66 20 74 69 | 6d 65 73 20 74 68 65 20 |er of ti|mes the |
|00005a00| 6f 70 65 72 61 74 69 6e | 67 20 73 79 73 74 65 6d |operatin|g system|
|00005a10| d5 73 20 73 74 6f 72 61 | 67 65 20 6d 61 6e 61 67 |.s stora|ge manag|
|00005a20| 65 6d 65 6e 74 20 73 65 | 72 76 69 63 65 73 20 61 |ement se|rvices a|
|00005a30| 72 65 20 75 73 65 64 20 | 69 73 20 76 61 73 74 6c |re used |is vastl|
|00005a40| 79 20 72 65 64 75 63 65 | 64 3a 20 61 6c 6c 6f 63 |y reduce|d: alloc|
|00005a50| 61 74 69 6f 6e 20 6e 6f | 77 20 69 6e 76 6f 6c 76 |ation no|w involv|
|00005a60| 65 73 20 6d 61 6e 69 70 | 75 6c 61 74 69 6e 67 20 |es manip|ulating |
|00005a70| 73 6f 6d 65 20 70 6f 69 | 6e 74 65 72 73 2c 20 77 |some poi|nters, w|
|00005a80| 68 69 63 68 20 69 73 20 | 66 61 72 20 66 61 73 74 |hich is |far fast|
|00005a90| 65 72 2e 0d 54 68 65 20 | 70 6f 6f 6c 20 61 62 73 |er..The |pool abs|
|00005aa0| 74 72 61 63 74 69 6f 6e | 20 61 6c 73 6f 20 70 72 |traction| also pr|
|00005ab0| 6f 76 69 64 65 73 20 74 | 68 65 20 66 6f 6c 6c 6f |ovides t|he follo|
|00005ac0| 77 69 6e 67 3a 0d a5 09 | 4f 70 65 72 61 74 69 6f |wing:...|Operatio|
|00005ad0| 6e 73 20 74 68 61 74 20 | 70 65 72 6d 69 74 20 61 |ns that |permit a|
|00005ae0| 20 63 6c 69 65 6e 74 20 | 74 6f 20 70 72 65 61 6c | client |to preal|
|00005af0| 6c 6f 63 61 74 65 20 61 | 20 63 68 75 6e 6b 20 6f |locate a| chunk o|
|00005b00| 66 20 6d 65 6d 6f 72 79 | 2c 20 69 6e 20 61 64 76 |f memory|, in adv|
|00005b10| 61 6e 63 65 20 6f 66 20 | 69 74 73 20 75 73 65 2e |ance of |its use.|
|00005b20| 20 0d a5 09 4f 70 65 72 | 61 74 69 6f 6e 73 20 74 | ...Oper|ations t|
|00005b30| 68 61 74 20 70 65 72 6d | 69 74 20 61 20 63 6c 69 |hat perm|it a cli|
|00005b40| 65 6e 74 20 74 6f 20 64 | 65 66 72 61 67 6d 65 6e |ent to d|efragmen|
|00005b50| 74 20 69 74 73 20 63 68 | 75 6e 6b 73 2c 20 61 6e |t its ch|unks, an|
|00005b60| 64 20 70 6f 73 73 69 62 | 6c 79 20 72 65 74 75 72 |d possib|ly retur|
|00005b70| 6e 20 75 6e 75 73 65 64 | 20 63 68 75 6e 6b 73 20 |n unused| chunks |
|00005b80| 62 61 63 6b 20 74 6f 20 | 74 68 65 20 68 65 61 70 |back to |the heap|
|00005b90| 2e 20 0d a5 09 4f 70 65 | 72 61 74 69 6f 6e 73 20 |. ...Ope|rations |
|00005ba0| 74 68 61 74 20 70 65 72 | 6d 69 74 20 61 20 63 6c |that per|mit a cl|
|00005bb0| 69 65 6e 74 20 74 6f 20 | 63 68 6f 6f 73 65 20 74 |ient to |choose t|
|00005bc0| 68 65 20 63 68 75 6e 6b | 20 73 69 7a 65 2c 20 73 |he chunk| size, s|
|00005bd0| 6f 20 61 73 20 74 6f 20 | 74 75 6e 65 20 61 6c 6c |o as to |tune all|
|00005be0| 6f 63 61 74 69 6f 6e 20 | 74 6f 20 74 68 65 20 6e |ocation |to the n|
|00005bf0| 65 65 64 73 20 6f 66 20 | 74 68 65 20 69 6d 70 6c |eeds of |the impl|
|00005c00| 65 6d 65 6e 74 61 74 69 | 6f 6e 20 28 66 6f 72 20 |ementati|on (for |
|00005c10| 65 78 61 6d 70 6c 65 2c | 20 74 6f 20 73 65 74 20 |example,| to set |
|00005c20| 61 20 63 68 75 6e 6b 20 | 73 69 7a 65 20 6f 70 74 |a chunk |size opt|
|00005c30| 69 6d 61 6c 20 66 6f 72 | 20 74 68 65 20 73 69 7a |imal for| the siz|
|00005c40| 65 20 6f 66 20 74 68 65 | 20 63 6c 61 73 73 65 73 |e of the| classes|
|00005c50| 20 62 65 69 6e 67 20 61 | 6c 6c 6f 63 61 74 65 64 | being a|llocated|
|00005c60| 2c 20 61 6e 64 20 74 6f | 20 6d 61 6b 65 20 63 68 |, and to| make ch|
|00005c70| 75 6e 6b 73 20 61 6c 69 | 67 6e 20 77 69 74 68 20 |unks ali|gn with |
|00005c80| 77 6f 72 64 20 62 6f 75 | 6e 64 61 72 69 65 73 29 |word bou|ndaries)|
|00005c90| 2e 0d 54 68 65 20 42 43 | 5f 43 50 6f 6f 6c 20 63 |..The BC|_CPool c|
|00005ca0| 6c 61 73 73 20 75 73 65 | 73 20 74 68 65 20 74 77 |lass use|s the tw|
|00005cb0| 6f 20 6e 65 73 74 65 64 | 20 63 6c 61 73 73 65 73 |o nested| classes|
|00005cc0| 20 42 43 5f 53 45 6c 65 | 6d 65 6e 74 20 61 6e 64 | BC_SEle|ment and|
|00005cd0| 20 42 43 5f 53 43 68 75 | 6e 6b 2e 20 45 61 63 68 | BC_SChu|nk. Each|
|00005ce0| 20 69 6e 73 74 61 6e 63 | 65 20 6f 66 20 74 68 65 | instanc|e of the|
|00005cf0| 20 70 6f 6f 6c 20 63 6c | 61 73 73 20 6d 61 6e 61 | pool cl|ass mana|
|00005d00| 67 65 73 20 61 20 6c 69 | 6e 6b 65 64 20 6c 69 73 |ges a li|nked lis|
|00005d10| 74 20 6f 66 20 42 43 5f | 53 43 68 75 6e 6b 20 6f |t of BC_|SChunk o|
|00005d20| 62 6a 65 63 74 73 20 77 | 68 69 63 68 20 61 72 65 |bjects w|hich are|
|00005d30| 20 61 63 74 75 61 6c 6c | 79 20 72 61 77 20 63 68 | actuall|y raw ch|
|00005d40| 75 6e 6b 73 20 6f 66 20 | 6d 65 6d 6f 72 79 2c 20 |unks of |memory, |
|00005d50| 62 75 74 20 61 72 65 20 | 74 72 65 61 74 65 64 20 |but are |treated |
|00005d60| 61 73 20 69 66 20 74 68 | 65 79 20 77 65 72 65 20 |as if th|ey were |
|00005d70| 74 68 65 6d 73 65 6c 76 | 65 73 20 6c 69 6e 6b 65 |themselv|es linke|
|00005d80| 64 20 6c 69 73 74 73 20 | 6f 66 20 42 43 5f 53 45 |d lists |of BC_SE|
|00005d90| 6c 65 6d 65 6e 74 20 69 | 6e 73 74 61 6e 63 65 73 |lement i|nstances|
|00005da0| 20 28 74 68 69 73 20 69 | 73 20 6f 6e 65 20 6f 66 | (this i|s one of|
|00005db0| 20 74 68 65 20 69 6d 70 | 6f 72 74 61 6e 74 20 73 | the imp|ortant s|
|00005dc0| 65 63 72 65 74 73 20 6d | 61 6e 61 67 65 64 20 62 |ecrets m|anaged b|
|00005dd0| 79 20 74 68 65 20 42 43 | 5f 43 50 6f 6f 6c 20 63 |y the BC|_CPool c|
|00005de0| 6c 61 73 73 29 2e 20 45 | 61 63 68 20 63 68 75 6e |lass). E|ach chun|
|00005df0| 6b 20 6d 61 79 20 6d 61 | 6e 61 67 65 20 65 6c 65 |k may ma|nage ele|
|00005e00| 6d 65 6e 74 73 20 6f 66 | 20 61 20 64 69 66 66 65 |ments of| a diffe|
|00005e10| 72 65 6e 74 20 73 69 7a | 65 2c 20 61 6e 64 20 73 |rent siz|e, and s|
|00005e20| 6f 20 66 6f 72 20 65 66 | 66 69 63 69 65 6e 63 79 |o for ef|ficiency|
|00005e30| 2c 20 74 68 65 20 6c 69 | 73 74 20 6f 66 20 63 68 |, the li|st of ch|
|00005e40| 75 6e 6b 73 20 69 73 20 | 73 6f 72 74 65 64 20 66 |unks is |sorted f|
|00005e50| 72 6f 6d 20 73 6d 61 6c | 6c 65 73 74 20 74 6f 20 |rom smal|lest to |
|00005e60| 6c 61 72 67 65 73 74 2e | 20 0d 4e 6f 74 69 63 65 |largest.| .Notice|
|00005e70| 20 74 68 61 74 20 74 68 | 65 20 42 43 5f 43 4d 61 | that th|e BC_CMa|
|00005e80| 6e 61 67 65 64 20 63 6c | 61 73 73 20 68 61 73 20 |naged cl|ass has |
|00005e90| 61 20 73 74 61 74 69 63 | 20 6d 65 6d 62 65 72 20 |a static| member |
|00005ea0| 6f 62 6a 65 63 74 20 6f | 66 20 74 68 65 20 42 43 |object o|f the BC|
|00005eb0| 5f 43 50 6f 6f 6c 20 63 | 6c 61 73 73 2e 20 54 68 |_CPool c|lass. Th|
|00005ec0| 75 73 2c 20 73 65 76 65 | 72 61 6c 20 75 6e 6d 61 |us, seve|ral unma|
|00005ed0| 6e 61 67 65 64 20 63 6f | 6e 63 72 65 74 65 20 73 |naged co|ncrete s|
|00005ee0| 74 72 75 63 74 75 72 65 | 73 20 63 61 6e 20 73 68 |tructure|s can sh|
|00005ef0| 61 72 65 20 74 68 65 20 | 73 61 6d 65 20 70 6f 6f |are the |same poo|
|00005f00| 6c 20 6f 66 20 73 74 6f | 72 61 67 65 2e 20 44 69 |l of sto|rage. Di|
|00005f10| 66 66 65 72 65 6e 74 20 | 75 6e 6d 61 6e 61 67 65 |fferent |unmanage|
|00005f20| 64 20 73 74 72 75 63 74 | 75 72 65 73 20 63 61 6e |d struct|ures can|
|00005f30| 20 6f 66 20 63 6f 75 72 | 73 65 20 64 65 66 69 6e | of cour|se defin|
|00005f40| 65 20 74 68 65 69 72 20 | 73 74 6f 72 61 67 65 20 |e their |storage |
|00005f50| 6d 61 6e 61 67 65 72 20 | 61 6e 64 20 68 65 6e 63 |manager |and henc|
|00005f60| 65 20 74 68 65 69 72 20 | 6f 77 6e 20 70 6f 6f 6c |e their |own pool|
|00005f70| 2c 20 74 68 75 73 20 67 | 69 76 69 6e 67 20 79 6f |, thus g|iving yo|
|00005f80| 75 20 63 6f 6d 70 6c 65 | 74 65 20 63 6f 6e 74 72 |u comple|te contr|
|00005f90| 6f 6c 20 6f 76 65 72 20 | 73 74 6f 72 61 67 65 20 |ol over |storage |
|00005fa0| 6d 61 6e 61 67 65 6d 65 | 6e 74 20 70 6f 6c 69 63 |manageme|nt polic|
|00005fb0| 79 2e 0d 53 65 61 72 63 | 68 69 6e 67 20 61 6e 64 |y..Searc|hing and|
|00005fc0| 20 73 6f 72 74 69 6e 67 | 0d 54 68 65 20 73 74 72 | sorting|.The str|
|00005fd0| 75 63 74 75 72 65 20 6f | 66 20 74 68 65 20 43 6f |ucture o|f the Co|
|00005fe0| 6c 6c 65 63 74 69 6f 6e | 73 20 63 6f 6d 70 6f 6e |llection|s compon|
|00005ff0| 65 6e 74 20 61 6c 6c 6f | 77 73 20 63 6c 61 73 73 |ent allo|ws class|
|00006000| 65 73 20 74 6f 20 61 63 | 74 20 61 73 20 61 67 65 |es to ac|t as age|
|00006010| 6e 74 73 20 74 68 61 74 | 20 61 72 65 20 72 65 73 |nts that| are res|
|00006020| 70 6f 6e 73 69 62 6c 65 | 20 66 6f 72 20 63 61 72 |ponsible| for car|
|00006030| 72 79 69 6e 67 20 6f 75 | 74 20 61 6c 67 6f 72 69 |rying ou|t algori|
|00006040| 74 68 6d 73 2e 20 53 75 | 63 68 20 61 67 65 6e 74 |thms. Su|ch agent|
|00006050| 73 2c 20 6f 72 20 74 6f | 6f 6c 73 2c 20 74 61 6b |s, or to|ols, tak|
|00006060| 65 20 61 64 76 61 6e 74 | 61 67 65 20 6f 66 20 70 |e advant|age of p|
|00006070| 61 74 74 65 72 6e 73 20 | 77 69 74 68 69 6e 20 63 |atterns |within c|
|00006080| 65 72 74 61 69 6e 20 66 | 61 6d 69 6c 69 65 73 20 |ertain f|amilies |
|00006090| 6f 66 20 61 6c 67 6f 72 | 69 74 68 6d 73 2e 20 54 |of algor|ithms. T|
|000060a0| 68 69 73 20 68 65 6c 70 | 73 20 75 6e 69 66 79 20 |his help|s unify |
|000060b0| 73 69 6d 69 6c 61 72 20 | 61 6c 67 6f 72 69 74 68 |similar |algorith|
|000060c0| 6d 73 20 61 6e 64 20 73 | 69 6d 70 6c 69 66 79 20 |ms and s|implify |
|000060d0| 74 68 65 69 72 20 69 6d | 70 6c 65 6d 65 6e 74 61 |their im|plementa|
|000060e0| 74 69 6f 6e 2e 0d 54 68 | 65 20 43 6f 6c 6c 65 63 |tion..Th|e Collec|
|000060f0| 74 69 6f 6e 73 20 63 6f | 6d 70 6f 6e 65 6e 74 20 |tions co|mponent |
|00006100| 70 72 6f 76 69 64 65 73 | 20 62 6f 74 68 20 73 65 |provides| both se|
|00006110| 61 72 63 68 69 6e 67 20 | 61 6e 64 20 73 6f 72 74 |arching |and sort|
|00006120| 69 6e 67 20 74 6f 6f 6c | 73 2e 20 0d 53 65 61 72 |ing tool|s. .Sear|
|00006130| 63 68 69 6e 67 20 61 20 | 73 74 72 75 63 74 75 72 |ching a |structur|
|00006140| 65 0d 54 68 65 20 43 6f | 6c 6c 65 63 74 69 6f 6e |e.The Co|llection|
|00006150| 73 20 63 6f 6d 70 6f 6e | 65 6e 74 20 70 72 6f 76 |s compon|ent prov|
|00006160| 69 64 65 73 20 73 65 76 | 65 72 61 6c 20 64 69 66 |ides sev|eral dif|
|00006170| 66 65 72 65 6e 74 20 6b | 69 6e 64 73 20 6f 66 20 |ferent k|inds of |
|00006180| 73 65 61 72 63 68 65 73 | 2e 20 61 73 20 66 6f 6c |searches|. as fol|
|00006190| 6c 6f 77 73 3a 0d a5 09 | 41 20 73 65 71 75 65 6e |lows:...|A sequen|
|000061a0| 74 69 61 6c 20 73 65 61 | 72 63 68 20 69 73 20 76 |tial sea|rch is v|
|000061b0| 65 72 79 20 73 69 6d 70 | 6c 65 20 79 65 74 20 69 |ery simp|le yet i|
|000061c0| 6e 65 66 66 69 63 69 65 | 6e 74 2e 20 49 6e 20 74 |nefficie|nt. In t|
|000061d0| 68 65 20 77 6f 72 73 74 | 20 63 61 73 65 2c 20 61 |he worst| case, a|
|000061e0| 20 73 65 61 72 63 68 20 | 65 78 65 63 75 74 65 73 | search |executes|
|000061f0| 20 6f 6e 20 74 68 65 20 | 6f 72 64 65 72 20 6f 66 | on the |order of|
|00006200| 20 4f 28 6e 29 2e 20 4f | 62 6a 65 63 74 73 20 6f | O(n). O|bjects o|
|00006210| 66 20 74 68 69 73 20 63 | 6c 61 73 73 20 6d 61 6b |f this c|lass mak|
|00006220| 65 20 6e 6f 20 61 73 73 | 75 6d 70 74 69 6f 6e 73 |e no ass|umptions|
|00006230| 20 61 62 6f 75 74 20 74 | 68 65 20 6f 72 64 65 72 | about t|he order|
|00006240| 20 6f 66 20 69 74 65 6d | 73 20 69 6e 20 74 68 65 | of item|s in the|
|00006250| 20 73 65 71 75 65 6e 63 | 65 2e 20 0d a5 09 41 6e | sequenc|e. ...An|
|00006260| 20 6f 72 64 65 72 65 64 | 20 73 65 61 72 63 68 20 | ordered| search |
|00006270| 69 73 20 66 61 73 74 65 | 72 20 28 69 74 20 65 78 |is faste|r (it ex|
|00006280| 65 63 75 74 65 73 20 6f | 6e 20 74 68 65 20 6f 72 |ecutes o|n the or|
|00006290| 64 65 72 20 6f 66 20 4f | 28 6e 2f 32 29 29 20 62 |der of O|(n/2)) b|
|000062a0| 75 74 20 61 73 73 75 6d | 65 73 20 74 68 61 74 20 |ut assum|es that |
|000062b0| 69 74 65 6d 73 20 69 6e | 20 74 68 65 20 73 65 71 |items in| the seq|
|000062c0| 75 65 6e 63 65 20 61 72 | 65 20 61 6c 72 65 61 64 |uence ar|e alread|
|000062d0| 79 20 73 6f 72 74 65 64 | 2e 0d a5 09 41 20 62 69 |y sorted|....A bi|
|000062e0| 6e 61 72 79 20 73 65 61 | 72 63 68 20 69 73 20 74 |nary sea|rch is t|
|000062f0| 68 65 20 66 61 73 74 65 | 73 74 20 28 69 74 20 65 |he faste|st (it e|
|00006300| 78 65 63 75 74 65 73 20 | 6f 6e 20 74 68 65 20 6f |xecutes |on the o|
|00006310| 72 64 65 72 20 6f 66 20 | 4f 28 6c 6f 67 20 6e 29 |rder of |O(log n)|
|00006320| 29 20 62 75 74 20 61 73 | 73 75 6d 65 73 20 74 68 |) but as|sumes th|
|00006330| 61 74 20 69 74 65 6d 73 | 20 69 6e 20 74 68 65 20 |at items| in the |
|00006340| 73 65 71 75 65 6e 63 65 | 20 61 72 65 20 61 6c 72 |sequence| are alr|
|00006350| 65 61 64 79 20 73 6f 72 | 74 65 64 2e 0d a5 09 41 |eady sor|ted....A|
|00006360| 20 62 69 6e 61 72 79 20 | 74 72 65 65 20 73 65 61 | binary |tree sea|
|00006370| 72 63 68 20 70 65 72 66 | 6f 72 6d 73 20 69 6e 2d |rch perf|orms in-|
|00006380| 6f 72 64 65 72 2c 20 70 | 72 65 2d 6f 72 64 65 72 |order, p|re-order|
|00006390| 2c 20 61 6e 64 20 70 6f | 73 74 2d 6f 72 64 65 72 |, and po|st-order|
|000063a0| 20 73 65 61 72 63 68 65 | 73 20 6f 6e 6c 79 20 6f | searche|s only o|
|000063b0| 6e 20 62 69 6e 61 72 79 | 20 74 72 65 65 20 73 74 |n binary| tree st|
|000063c0| 72 75 63 74 75 72 65 73 | 2e 0d 45 78 63 65 70 74 |ructures|..Except|
|000063d0| 20 66 6f 72 20 74 68 65 | 20 62 69 6e 61 72 79 20 | for the| binary |
|000063e0| 74 72 65 65 20 73 65 61 | 72 63 68 2c 20 61 6c 6c |tree sea|rch, all|
|000063f0| 20 6f 66 20 74 68 65 73 | 65 20 73 65 61 72 63 68 | of thes|e search|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
